← 返回题目列表

AtCoder · future_contest_2020_final_2_a

A. 千树2

中文机器翻译题面 查看原题

问题文本的更改

  • K 不再固定,并且针对每棵树而变化。 给出 K_i ,2 以上 100 现在给出以下顶点树:
  • c_i 的生成公式已更改。中等顶点比例减少,弱顶点数量增加,c_i 总体上正在减少。 二维坐标平面上的

問題文

在二维坐标平面上 N 顶点,顶点 1, \ldots, N 。另外,S 无向树 T_1, \ldots, T_S 。 对于

你的任务是在平面上绘制一些连接顶点的边。 N 顶点无向图 创建 G 并 它的意思是“取出”G 减去 S 图表。提取的图 与 T_1, \ldots, T_S 越相似,得分越高。各项目的详细内容如下所述。

  • 关于平面上的顶点:顶点 i (1 \leqq i \leqq N) 的坐标是 (x_i, y_i) 所有这些坐标都是 小于或等于 0 以上 1000 的整数。此外,每个顶点都有一个正整数值 电源 被定义并且顶点 i 的幂是 关于 c_i 。

  • 木 T_1, \ldots, T_S : 编号为1, \ldots, K 它是一个具有 K_i 顶点的无向树。为了方便起见,这些树都编号了 1 的顶点,并且该树 T_i (1 \leqq i \leqq S) 中的数字 j (2 \leqq j \leqq K_i) 顶点的父级是数字 这是 p_{i,j} 的顶点。

  • 关于添加边:要创建的图形 G 有 直到 0 本以上 100000 。然而,侧面 要拉伸 \{i, j\} (i \neq j) ,顶点 i, j 之间的欧几里得距离 必须小于或等于 c_i + c_j 。此外,不得出现自边缘或多重边缘。

  • 关于检索图:每棵树 对于 T_i (1 \leqq i \leqq S) ,G 请注明 K_i 頂点 V_{i,1}, \ldots, V_{i,K_i} 。这对于每个 对于 j (1 \leqq j \leqq K_i) 关于,向上游 V_{i,j} 该值应乘以 T_i 号码 j 的顶点。同一顶点可用于多棵树。

  • 关于评分:每棵树 计算 T_i (1 \leqq i \leqq S) 的分数如下,S 树的分数总和就是该测试用例的分数。

  • 一些整数 关于 x, y (1 \leqq x, y \leqq K_i) 存在, 由T_i 是边缘 有 \{x, y\} 当您没有 G 是边缘 有 \{V_{i,x}, V_{i,y}\} 时: 0 点

  • 否则,整数集 (x, y) (1 \leqq x, y \leqq K_i) ,成为G 是边缘 有 \{V_{i,x}, V_{i,y}\} 当您没有 T_i 是边缘 有 \{x, y\} 的项目数是 当 e_i 。

    • e_i = 0 时: 100 点
    • e_i = 1 时: 10 点
    • e_i = 2 时: 1 点
    • e_i \geqq 3 时: 0 点

制約

  • N = 1000
  • S = 1000
  • 2 \leqq K_i \leqq 100
  • 0 \leqq x_i, y_i \leqq 1000
  • 1 \leqq c_i \leqq 1500
  • 1 \leqq p_{i,j} \leqq j-1
  • 所有输入值都是整数。

入力

输入是按以下格式从标准输入给出的。

N S
x_1 y_1 c_1
x_2 y_2 c_2
:
x_N y_N c_N
K_1 p_{1,2} p_{1,3} \ldots p_{1,K_1}
K_2 p_{2,2} p_{2,3} \ldots p_{2,K_2}
:
K_S p_{S,2} p_{S,3} \ldots p_{S,K_S}

出力

按以下格式输出。 类似于

M
A_1 B_1
A_2 B_2
:
A_M B_M
V_{1,1} V_{1,2} \ldots V_{1,K_1}
V_{2,1} V_{2,2} \ldots V_{2,K_2}
:
V_{S,1} V_{S,2} \ldots V_{S,K_S}

这是创建的图表 G 是 在 M (0 \leqq M \leqq 100000) 书的侧面 输出 \{A_1, B_1\}, \{A_2, B_2\}, \ldots, \{A_M, B_M\} (1 \leqq A_i, B_i \leqq N) 。边可以按任何顺序输出,并且每条边的端点可以按任何顺序输出。V_{i,j} (1 \leqq V_{i,j} \leqq N) ,请参阅问题正文。

测试用例是 50 。对于每个测试用例,将按照问题文本中的书写方式计算分数,所有测试用例的总分将是该提交的分数。

违反上述格式或具有其他缺陷(例如,存在自边、多边、一次读取中出现重复顶点)的输出可能会被判断为“不正确”。在这种情况下,如果测试用例作为输入示例给出,则该测试用例的分数为 0 点。其他的测试点的话,除了输入例以外的所有测试点的得分都 0 点。

测试用例生成方法

  • 各頂点 i (1 \leqq i \leqq N) 的坐标 x_i, y_i 分别是 0 以上 1000 从以下整数中均匀随机选择。这些 2N 坐标全部独立选择,即使多个点匹配,也不会重新绘制。

  • 各頂点 i (1 \leqq i \leqq N) 是 可以表示为5概率为 % 強頂点、10概率为 % 中頂点、85概率为 % 弱頂点 变为。基于此,c_i 是从以下整数范围中均匀随机选择的。 对于

  • 強頂点: 200 以上 500 以下

  • 中頂点: 50 以上 200 以下
  • 弱頂点: 1 以上 50 以下

  • 各 i, j (1 \leqq i \leqq S, 2 \leqq j \leqq K_i) ,木材 T_i 号码 j 顶点的父级 p_{i,j} 是 您也可以写 1 以上 j - 1 从以下整数中均匀随机选择。

入出力例

输入例和输出例可以从 这个链接 可以从 下载。