故事
AtCoder 是一家大型科技公司,拥有许多办事处。 为了安全地共享未来竞赛的问题陈述的超级机密信息,我们决定在办公室之间使用量子加密技术建立专用线路。 有多个候选办公室对可以通过专线连接,我们希望确保所有办公室都通过专线连接。 建立专线的成本与线路的长度成正比,但由于物理限制,并不总是能够建立一条直线,因此我们要求供应商估算每个候选者的确切成本。 由于高桥首席执行官缺乏耐心,一旦收到对一位候选人的评估,他就会立即决定是否设立这条线。 请大家支持高桥,帮助他以尽可能低的成本实现自己的目标。
问题陈述
给你一个无向图 N 顶点和 M 边缘。 每个顶点都在二维平面上,其坐标 i第一个顶点是 (x_i, y_i)。 的 i第一条边连接顶点 u_i 和 v_i,并且我们事先知道它的长度 l_i 满足 d_i \leq l_i \leq 3 d_i,其中 d_i=\mathrm{round}(\sqrt{(x_{u_i}-x_{v_i})^2+(y_{u_i}-y_{v_i})^2}) 是端点之间的欧氏距离,四舍五入到最接近的整数。
真实边长 l_i 将按顺序一一给出 i=0 to i=M-1。 收到长度后 l_i 的 i第一条边,在收到长度之前必须决定是否采用该边 下一个边缘的 l_{i+1} 。
让 S 是您最终采用的集合边,然后对于每个顶点对 (u,v), S 必须包含之间的路径 u 和 v。 请做出决定,使所采用的边的总长度尽可能短。
输入和输出
对于所有测试用例,我们修复 N=400 和 M=1995.
执行开始时,坐标 N 顶点 (x_0,y_0), \cdots, (x_{N-1},y_{N-1}) 和端点 M 边缘 (u_0,v_0), \cdots, (u_{M-1},v_{M-1}) 由标准输入以以下格式给出。
x_0 y_0
\vdots
x_{N-1} y_{N-1}
u_0 v_0
\vdots
u_{M-1} v_{M-1}
保证满足以下条件。
- 0\leq x_i,y_i\leq 800
- 0\leq u_i<v_i\leq N-1
- 相同 (u_i,v_i) 对从未出现多次。
- 该图已连接。
然后,重复以下过程 M 次。
在 i-th (0\leq i\leq M-1)过程,长度 l_i 的 i第一条边是从之间的整数均匀随机生成的 d_i 和 3 d_i,并在一行中提供给标准输入。
读完后 l_i,输出 1 如果您采用 i第边缘,或 0 如果不这样做,请在一行中连接到标准输出。
请注意,直到程序输出 0 或 1 后才会给出下一个输入。输出之后,您必须刷新标准输出。 否则,提交的内容可能会被判定为 TLE .
示例
| i | 输入 | 输出 |
|---|---|---|
| 先前信息 | 406 19 347 786 \vdots 21 191 |
|
| 0 | 69 |
1 |
| 1 | 89 |
0 |
| \vdots | ||
| M-1 | 175 |
0 |
评分
让 A 是所采用的边集的总长度, B 是在真实长度满足的条件下最优边集的总长度 每条边的 l_i 都是预先知道的(最小生成树)。 然后,你将获得分数 \mathrm{round}(10^8\times B/A)。 当采用的边集合不能使图连通时,您的提交将被判定为 WA。 注意,如果你的程序异常终止,可能会被判断为 WA 而不是 RE.
有150个测试用例,提交的分数是每个测试用例的总分。如果您得到的结果不是 AC 对于一个或多个测试用例,提交的分数将为零。比赛时间内获得的最高分将决定最终排名,比赛结束后不进行系统测试。如果超过一名参赛者获得相同分数,则排名将根据获得该分数的提交作品的提交时间来确定。
输入生成
让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包括在内。
的生成 (x_i,y_i)
对于每个 i=0,\cdots,N-1,我们生成 x_i=\mathrm{rand}(0,800) 和 y_i=\mathrm{rand}(0,800)。 如果到坐标的欧氏距离 已生成顶点的 (x_j,y_j) 已经生成的顶点 (j<i) 小于或等于 5,我们再生 (x_i,y_i).
的生成 (u_i,v_i)
让 G 是一个具有边长的完整图 \mathrm{round}(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}) 顶点之间 i 和 j。 通过重复以下过程 5 次,我们生成一组 E of M=5(N-1) 边缘。
我们计算最小生成树 T of G,并删除所有边 T 来自 G 并将它们插入 E.
最后,通过随机打乱边的顺序 E,我们生成边列表 (u_0,v_0),\cdots,(u_{M-1},v_{M-1}).
的生成 l_i
让 d_i=\mathrm{round}(\sqrt{(x_{u_i}-x_{v_i})^2+(y_{u_i}-y_{v_i})^2}) 是端点之间的欧氏距离,四舍五入到最接近的整数。 然后我们生成 l_i=\mathrm{rand}(d_i,3 d_i).