AT_ahc036_a [AHC036A] Efficient Signal Control

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_A$ 的内容覆盖 $R_B$ 的内容。 现在，喜欢旅行的 X 计划在 Y 国旅行。 X 有一个旅行计划，即城市顶点编号的列表 $t_0,\ t_1,\ \ldots,\ t_{T-1}$，希望按顺序访问这些城市。列表中可能包含同一个城市多次，但不会有连续重复的城市。 X 以城市 $0$ 作为当前所在位置开始旅行。首先，X 可以请求 Y 国交通大臣，将用于信号灯控制的数组 $A$ 的内容设置为任意值。此后，$A$ 的内容不可再更改。 之后，X 可以按任意顺序、任意次数（不超过 $10^5$ 次）重复进行如下**信号操作**或**移动**。具体操作示例见下方“输出示例”部分。 - 信号操作 - 请求 Y 国交通大臣进行一次上述信号灯操作，改变信号灯状态。 - 移动 - 从当前所在城市移动到直接通过道路相连的某个城市，并将当前位置更新为该城市。移动目标城市的信号灯必须在此时为蓝色。 若能按计划顺序访问旅行计划中的所有城市，则 X 的旅行视为成功。 更严格地说，记 X 依次到达的城市为 $c_0 = 0, c_1, \ldots$，存在一个严格单调递增的长度为 $T$ 的非负整数序列 $(i_0, i_1, \ldots, i_{T-1})$，使得 $c_{i_j} = t_j\ (0 \leq j \leq T-1)$，则且仅则 X 的旅行成功。 由于 Y 国交通大臣非常繁忙，X 希望尽量减少信号操作的次数。 请合理设置数组 $A$ 的元素，并设计信号操作和移动的顺序，使旅行能以尽可能少的信号操作次数成功完成。

输入通过标准输入按以下格式给出。 ``` 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} ``` - 第 1 行包含 5 个用空格分隔的整数 $N, M, T, L_A, L_B$。 - $N$：城市数，$N=600$。 - $M$：道路数，满足 $N-1 \leq M \leq 3N-6$。 - $T$：要访问的城市数，$T=600$。 - $L_A$：用于信号控制的数组 $A$ 的长度，$N \leq L_A \leq 2N$。 - $L_B$：用于信号控制的数组 $B$ 的长度，$4 \leq L_B \leq 24$。 - 接下来 $M$ 行，每行描述一条道路，第 $i$ 行为 $u_i~v_i$，表示城市 $u_i$ 和 $v_i$ 之间有一条双向道路。$0 \leq u_i < v_i \leq N-1$，且 $(u_i, v_i) \neq (u_j, v_j)\ (i \neq j)$。 - 接下来 1 行，包含 $T$ 个用空格分隔的整数 $t_0, t_1, ..., t_{T-1}$，表示 X 计划访问的城市，$0 \leq t_i \leq N-1\ (0 \leq i \leq T-1)$，$t_0 \neq 0$，$t_i \neq t_{i+1}\ (0 \leq i \leq T-2)$。 - 接下来 $N$ 行，每行描述城市 $i$ 的坐标 $(x_i, y_i)$，坐标为整数，$0 \leq x_i, y_i \leq 1000$，且 $(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$。此部分仅用于可视化，如不需要可忽略。 保证给定的图是连通的平面图。将顶点 $i$ 放在坐标 $(x_i, y_i)$，每条边画为两端点的线段时，任意两条边除端点外无公共点。 ##

第 1 行输出 $A$ 的初始值，即 $L_A$ 个 $0$ 到 $N-1$ 的整数，用空格分隔。 接下来每行输出一次操作，格式如下： - 若为信号操作 设 $R_A, R_B$ 的长度为 $l\ (1 \leq l \leq L_B)$，$R_A$ 的起始位置为 $P_A\ (0 \leq P_A \leq L_A - l)$，$R_B$ 的起始位置为 $P_B\ (0 \leq P_B \leq L_B - l)$，则输出： ``` s l P_A P_B ``` - 若为移动 设移动目标城市编号为 $v$，则输出： ``` m v ``` 移动目标城市必须与当前位置直接相连，且此时信号灯为蓝色。 [查看示例](https://img.atcoder.jp/ahc036/e5f02df53f30d36e.html?lang=ja&output=sample) # 输出格式 （略，见上文）

### 得分 若旅行成功，信号操作次数为 $C$，则绝对得分为 $C$。绝对得分越小越好。 若旅行未成功、操作不合法、操作次数超过 $10^5$，则判为 WA。 每个测试用例的相对得分为 $\text{round}(10^9 \times \left(\frac{\text{全体参赛者中的最小绝对得分}}{\text{你的绝对得分}}\right))$，所有用例的相对得分之和为提交得分。 最终排名以赛后系统测试的得分为准。系统测试和暂定测试均有部分用例输出不合法或超时时，该用例的相对得分为 0，并从“全体参赛者中的最小绝对得分”计算中剔除。系统测试只对最后一次非 CE 的提交进行，请注意最终提交的正确性。 #### 测试用例数 - 暂定测试：50 个 - 系统测试：2000 个 - 赛后将公开 [seeds.txt](https://img.atcoder.jp/ahc036/seeds.txt) (sha256=`607aca150bd5f8f062937b02e6d14c15f7661aefbd279f150043e6d7e47f8d3c`) #### 相对评价系统说明 暂定测试和系统测试均只计入最后一次非 CE 的提交。 每个用例的全体参赛者最小绝对得分也只取当前排行榜上的最终提交。 排行榜显示的是相对得分，每次新提交都会重新计算相对得分。 提交列表中显示的分数是各用例绝对得分之和，不显示相对得分。若想知道非最新提交在当前排行榜下的相对得分，需要重新提交。输出不合法或超时时，提交列表分数为 0，但排行榜会显示正确用例的相对得分之和。 #### 关于运行时间 运行时间会有一定波动。系统测试时因并发执行较多，运行时间可能比暂定测试略长。请在程序内自行计时或预留充足时间，避免系统测试 TLE。 ### 输入生成方法 详细生成方法如下。记 $L$ 到 $U$ 间的均匀随机整数为 $\mathrm{rand}(L, U)$，$L$ 到 $U$ 间的均匀随机实数为 $\mathrm{rand\_double}(L, U)$。两点 $u, v$ 的距离为 $\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$： 1. 随机生成 $x_i = \mathrm{rand}(0,1000), y_i = \mathrm{rand}(0,1000)$。 2. 若 $V$ 中存在与 $(x_i, y_i)$ 距离小于 $D_{vmin}$ 的点，则重新选取。 3. 将 $(x_i, y_i)$ 加入 $V$。 边集 $E$ 生成如下： 1. 枚举所有距离 $\leq D_{emax}/2$ 的点对，随机排序，依次加入 $E$，若与已加入的边无交则加入。边交指两边除端点外有公共点。 2. 枚举所有距离 $> D_{emax}/2$ 且 $\leq D_{emax}$ 的点对，随机排序，依次加入 $E$，若与已加入的边无交则加入。 若此时图 $(V, E)$ 不连通，则重头生成 $V$。 最后，按随机顺序遍历 $E$，若去掉 $e$ 后图仍连通，则以概率 $P_{remove}$ 删除 $e$。 #### $t$ 的生成 $t_0$ 随机取 $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, 2N)$。 $L_B = \mathrm{floor}(\mathrm{rand\_double}(2.0, 5.0)^2)$，$\mathrm{floor}(x)$ 表示不大于 $x$ 的最大整数。 无需完全理解上述内容。 详细实现见输入生成器源码。 ### 工具 ### 样例解释 1 本输入仅用于说明，未必满足输入约束。 输出说明及可视化： ``` 0 1 3 4 5 6 2 ``` 将 $A$ 的初始值设为 $[0, 1, 3, 4, 5, 6, 2]$。初始时所有信号灯为红色。 ``` s 4 0 0 ``` 将 $A$ 的第 $0$ 个元素起的长度为 $4$ 的子区间，覆盖 $B$ 的第 $0$ 个元素起的区间。此时 $B = [0, 1, 3, 4]$。 ``` m 3 m 4 ``` 依次从 $0 \to 3 \to 4$ 移动，达到第一个目的地。 # 提示 （略，见上文） 由 ChatGPT 4.1 翻译