← 返回题目列表

AtCoder · ahc036_a

A. 高效信号控制

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

问题陈述

Y 国有 N 城市和 M 道路,其中 i第条路连接城市 u_i 和城市 v_i 双向。所有道路都不相交,由城市和道路组成的图是平面图。

每个城市都有一个 交通信号 控制进城交通。 信号有两种状态: 红色 和 绿色。你可以搬到城市 v 仅当城市中有信号时 v 为绿色。 (您要离开的城市的信号可以处于任一状态。)

Y国城市的交通信号灯由数组管理 A 和 B.

数组 A 的长度为 L_A,每个元素都是介于 0 和 N-1,包括在内。
数组 B 的长度为 L_B,最初,所有元素都是 -1.

具体来说,数组 B 代表交通信号的状态。如果数组 B 包含值 v,则城市信号 v 为绿色。如果数组 B 不包含该值 v,则城市信号 v 为红色。
数组 A 用于控制数组 B。通过执行以下操作,您可以使用数组中的值 A 更改数组的内容 B 从而改变信号的状态:

  1. 从中选择一个连续的子数组 A 并调用它 R_A.
  2. 从中选择一个连续的子数组 B 的长度与 R_A 并调用它 R_B.
  3. 覆盖内容 R_B 的内容 R_A.

旅行爱好者 X 正在计划前往 Y 国旅行。
X 有一个城市顶点编号列表 t_0, t_1, \ldots, t_{T-1} 他想按顺序访问。同一城市可能会在列表中多次出现,但同一城市不会连续出现。

X从城市开始旅程 0。最初,X 要求他的朋友,Y 国的交通部长,设置数组的内容 A 为任何所需值。之后,数组的内容 A 无法更改。
然后,X 可以重复以下操作 信号操作 or 动作 最多 10^5 次,顺序不限。有关信号操作和移动的具体示例,请参阅下面的“示例输出”部分。

  • 信号操作
    • 要求Y国交通部长执行一次上述信号操作,改变信号状态。
  • 运动
    • 从当前城市移动到有道路直接连接的城市之一,并将当前城市更新为目的地城市。目的地城市的信号灯必须是绿色的。

如果X能够按照列出的顺序访问旅行计划中的所有城市,则旅行成功。
更准确地说,如果存在严格递增的非负整数序列 (i_0, i_1, \ldots, i_{T-1}) 长度 T 这样 c_{i_j} = t_j (0 \le j \le T - 1),其中 X 访问的城市序列为 c_0 = 0, c_1, \ldots,则行程成功。

Y 国交通部长非常忙碌,因此 X 希望尽量减少信号操作次数。
请确定数组的元素 A,并以最少信号操作次数成功跳闸的方式执行信号操作和运动。


评分

当跳闸成功且信号操作次数表示为 C,您将获得绝对分数 C。绝对分数越低越好。

如果跳闸不成功,或者存在无效的信号操作/动作,或者信号操作和动作的次数超过 10^5,判断结果为 WA.

对于每个测试用例, \(\text{round}(10^9\times\left(\frac{\rm{\所有\参与者中的\绝对\得分\最小值}}{\rm{你的\绝对\得分}}\right)) \) 获得 相对评价分数,相对评价分数之和即为提交的分数。

最终排名将由比赛结束后系统进行更多投入的测试来决定。无论是临时测试还是系统测试,如果您提交的测试用例产生了非法输出或超出了某些测试用例的时限,则只有这些测试用例的相对评估分数将为0,您的提交将被排除在计算之外 所有参与者的最低绝对分数 对于这些测试用例。

系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。

测试用例数量

  • 临时测试:50
  • 系统测试:2000
    • 我们将发布 种子.txt (sha256=607aca150bd5f8f062937b02e6d14c15f7661aefbd279f150043e6d7e47f8d3c) 比赛结束后。

关于相关评价体系

在临时/系统测试中,排名将仅使用收到除以下结果之外的最后提交的结果来计算: CE.
仅使用最后提交的内容来计算 所有参与者的最低绝对分数 为每个测试用例计算相对评估分数时。

排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。
另一方面,提交页面上显示的每个提交的分数是每个测试用例的评估值的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。

关于执行时间

每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或确保有足够的执行时间。


输入

输入将从标准输入以以下格式提供。

\(
N ~ M ~ T ~ L_A ~ L_B \\
u_0 ~ v_0 \\
\vdots \\
u_{M-1} ~ v_{M-1} \\
t_{0} ~ t_{1} ~ \ldots ~ t_{T-1} \\
x_0 ~ y_0 \\
\vdots \\
x_{N-1} ~ y_{N-1} \)
  • 第一行有五个整数 N,M,T,L_A,L_B 以空格分隔。
    • N 代表城市数量,满足 N = 600.
    • M 代表道路数量,满足 N-1 \le M \le 3 \times N-6.
    • T 是访问的城市数量,满足 T = 600.
    • L_A 表示数组的长度 A 用于控制信号并满足 N \le L_A \le 2 \times N.
    • L_B 表示数组的长度 B 用于控制信号并满足 4 \le L_B \le 24.
  • 以下 M 行包含有关道路的信息。的 i第条路连接城市 u_i 和 v_i 双向。 0 \le u_i \lt v_i \le N - 1, (u_i, v_i) \neq (u_j, v_j) (i \neq j) 很满意。
  • 以下行包含 T 由空格分隔的整数。 t_0, t_1, ..., t_{T - 1} 是 X 计划访问的城市,并且 0 \le t_i \le N - 1 (0 \le i \le T - 1), t_0 \neq 0, t_i \neq t_{i+1} (0 \le i \le T - 2) 很满意。
  • 以下 N 行包含城市的坐标 i as (x_i, y_i) 用于可视化工具。坐标是整数并且 0 \le x_i, y_i \le 1000, (x_i, y_i) \neq (x_j, y_j) (i \neq j) 很满意。如果不需要,您可以跳过阅读它们。
给定的图是连通平面图,并且当顶点 i 放置在坐标处 (x_i, y_i) 并且每条边被绘制为连接其端点的线段,保证没有两条边除了端点之外有公共点。

输出

第一行,输出初始值 A as L_A 之间的整数 0 和 N - 1,包含以空格分隔。

在后续行中,按以下格式输出操作。

  • 执行信号操作时
    如果长度 R_A 和 R_B is l (1 \le l \le L_B), 的起始位置 R_A is P_A (0 \le P_A \le L_A - l), 和起始位置 R_B is P_B (0 \le P_B \le L_B - l), 然后输出 l, P_A, P_B 前导后用空格分隔 s.
    s l P_A P_B
  • 移动时
    如果目的地城市是 v, 然后输出 v 前导后用空格分隔 m.
    m v
    请注意,目的地城市必须与当前城市有道路直接相连,且当时其信号灯必须为绿色。

显示示例

输入生成

输入生成的详细信息

让 \mathrm{rand}(L,U) 是一个生成均匀随机整数的函数 L 和 U,包含在内,并且 \mathrm{rand\_double}(L,U) 是一个生成大于或等于的均匀随机实数的函数 L 且小于 U。 另外,设两个顶点的距离 u, v be \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}.

图形生成

生成参数 D_{vmin}, D_{emax},和 P_{remove} 使用 分别为 \mathrm{rand}(20, 30), \mathrm{rand}(80, 140),和 \mathrm{rand\_double}(0.0, 0.5) 。

设置 N = 600 并按顺序执行以下操作 i = 0, 1, \ldots N - 1 生成顶点集 V.

  1. 生成 x_i = \mathrm{rand}(0,1000), y_i = \mathrm{rand}(0,1000).
  2. 继续选择 (x_i, y_i) 直到没有顶点 V 距离小于 D_{vmin} to (x_i, y_i).
  3. 添加 (x_i, y_i) to V.

生成边缘集 E 如下:

  1. 列出距离为 D_{emax} / 2,随机洗牌,并将每对添加到 E 如果它们不与任何已添加的边相交。这里,边相交意味着如果顶点 i 放置在坐标处 (x_i, y_i) 并且边被绘制为连接其端点的线段,两条边共享除端点之外的公共点。
  2. 列出距离大于的所有顶点对 D_{emax} / 2 但小于 D_{emax},随机洗牌,并将每对添加到 E 如果它们不与任何已添加的边相交。

如果图表 (V, E) 此时未连接,从创建顶点集开始重新生成 V.

最后,对于每条边 e \in E 以随机顺序排列,如果图形在删除后仍然保持连接 e,删除 e 来自 E 的概率为 P_{remove}.

的一代 t

生成 t_0 与 \mathrm{rand}(1, N - 1).

对于 i = 1, 2, \ldots, T - 1,生成 t_i 从之间的所有整数中均匀随机选择 0 和 N - 1,包括除 t_{i -1}.

的一代 L_A 和 L_B

生成 L_A 使用 分别为 \mathrm{rand}(N, 2 \times N).

生成 L_B 使用 分别为 \mathrm{floor}{(\mathrm{rand\_double}(2.0, 5.0)^2)}。在这里, \mathrm{floor}{(x)} 表示小于等于的最大整数 x.

您无需通读。
请参阅输入生成器的源代码以了解实现细节。

工具

请注意,在比赛结束之前禁止共享可视化结果或讨论解决方案和注意事项。

本地测试器将程序的输出直接写入输出文件。
您的程序可能会输出以以下开头的注释行 #。 可视化工具的 Web 版本显示注释行以及相应的输出,这对于调试和分析可能很有用。 由于判断程序会忽略所有注释行,因此您可以提交按原样输出注释行的程序。


示例输入

7 9 3 7 4
0 1
0 2
0 3
1 2
2 3
3 4
4 5
5 6
6 0
4 1 5
100 0
200 0
200 100
100 100
0 200
0 100
0 0
请注意,此输入用于解释目的,因此不满足输入的所有限制。

示例输出

0 1 3 4 5 6 2
s 4 0 0
m 3
m 4
m 3
m 0
m 1
s 2 4 2
m 0
m 6
m 5
输出 说明 可视化
0 1 3 4 5 6 2
设置初始值 A to [0, 1, 3, 4, 5, 6, 2].
最初,所有信号均为红色。
s 4 0 0
覆盖 length 的子数组 4 从 0- 第一个元素 B,子数组从 0- 第一个元素 A。的价值 B 变为 [0, 1, 3, 4].
m 3
m 4
移动到顺序中的第一个目标顶点 0 → 3 → 4.
m 3
m 0
m 1
然后,按顺序移动到下一个目标顶点 4 → 3 → 0 → 1.
s 2 4 2
覆盖 length 的子数组 2 从 2-nd 元素 B,子数组从 4- 第一个元素 A。的价值 B 变为 [0, 1, 5, 6].
m 0
m 6
m 5
按顺序移动到最终目标顶点 1 → 0 → 6 → 5.
该测试用例的分数是 2 因为信号操作被执行了两次。