{"problem":{"name":"[JOIST 2024] 间谍 3 / Spy 3","description":{"content":"  Aoi 和 Bitaro 是 JOI 国 国家情报局的间谍。这次他们的任务是对 IOI 国 进行潜入调查。Bitaro 潜入 IOI 国，而 Aoi 在 JOI 国 向 Bitaro 发出指示。 潜入前，Aoi 和 Bitaro 得到了 IOI 国 的一张地图。IOI 国 有 $N$ 个城市，编号为 $0$ 到 $N-1$。此外，IOI 国 有 $M$ 条道路，编号为 $0$ 到 $M-1","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10434"},"statements":[{"statement_type":"Markdown","content":"Aoi 和 Bitaro 是 JOI 国 国家情报局的间谍。这次他们的任务是对 IOI 国 进行潜入调查。Bitaro 潜入 IOI 国，而 Aoi 在 JOI 国 向 Bitaro 发出指示。\n\n潜入前，Aoi 和 Bitaro 得到了 IOI 国 的一张地图。IOI 国 有 $N$ 个城市，编号为 $0$ 到 $N-1$。此外，IOI 国 有 $M$ 条道路，编号为 $0$ 到 $M-1$。第 $i$ 条道路（$0 \\le i \\le M-1$）双向连接城市 $A_i$ 和城市 $B_i$，长度为 $C_i$。通过若干条道路可以在任意两座城市之间往来。Bitaro 在 IOI 国 内通过这些道路在城市间移动。另外，共有 $Q$ 个调查计划。第 $j$ 个计划（$0 \\le j \\le Q-1$）要调查 IOI 国 的城市 $T_j$。\n\n以上信息最初同时告知了 Aoi 和 Bitaro。随后，Bitaro 开始潜入 IOI 国。\n\nBitaro 设法甩开了无数追兵，击败了刺客，最终成功潜入 IOI 国 的城市 $0$。然而，由于潜入行动极其艰难，Bitaro 遗失了关于 IOI 国 的部分信息。具体而言，Bitaro 丢失了 $K$ 条道路的长度信息，即道路 $X_0, X_1, \\dots, X_{K-1}$。换言之，Bitaro 已不知道 $C_{X_0}, C_{X_1}, \\dots, C_{X_{K-1}}$ 的数值。注意，尽管 Bitaro 丢失了这些信息，Aoi 仍然掌握它们。\n\nBitaro 立刻向 Aoi 报告了他所遗失的道路长度信息是哪些。\n\n为了完成任务，Bitaro 希望从城市 $0$ 出发，分别找到到每个被 $Q$ 个调查计划锁定的城市的最短路径。\n\nAoi 将向 Bitaro 发送一个只包含字符 ‘0’ 或 ‘1’ 的字符串以协助他。由于存在被截获的风险，Aoi 希望尽量减少发送的内容。\n\n给定关于 IOI 国 的信息、调查计划以及 Bitaro 所遗失信息的道路，请编写程序实现 Aoi 的发送策略；同时，编写程序实现 Bitaro 在其掌握的信息与 Aoi 发送的字符串下寻找最短路径的策略。\n\n### 实现细节\n\n你需要提交 $2$ 个文件。\n\n第一个文件为 `Aoi.cpp`。该文件用于实现 Aoi 的策略，并应实现以下函数。程序需通过预处理指令 `#include` 包含 `Aoi.h`。\n\n* `std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)`\n\n此函数在每个测试用例中只被调用一次。\n* 参数 $N$ 是 IOI 国 中的城市数量。\n* 参数 $M$ 是 IOI 国 中的道路数量。\n* 参数 $Q$ 是调查计划的数量。\n* 参数 $K$ 是 Bitaro 遗失长度信息的道路条数。\n* 参数 $A, B, C$ 为长度为 $M$ 的数组。表示第 $i$ 条道路（$0 \\le i \\le M-1$）双向连接城市 $A[i]$ 与城市 $B[i]$，长度为 $C[i]$。\n* 参数 $T$ 为长度为 $Q$ 的数组。表示第 $j$ 个计划（$0 \\le j \\le Q-1$）要调查的城市为 $T[j]$。\n* 参数 $X$ 为长度为 $K$ 的数组。表示 Bitaro 遗失长度信息的道路为 $X[0], X[1], \\dots, X[K-1]$。\n* 返回值为 Aoi 向 Bitaro 发送的字符串 $s$。\n* 字符串 $s$ 的每个字符必须是 ‘0’ 或 ‘1’。若不满足此条件，你的程序将被判定为 **Wrong Answer [1]**。\n* 字符串 $s$ 的长度最多为 $12000$。若不满足此条件，你的程序将被判定为 **Wrong Answer [2]**。\n\n第二个文件为 `Bitaro.cpp`。该文件用于实现 Bitaro 的策略，并应实现以下函数。程序需通过预处理指令 `#include` 包含 `Bitaro.h`。\n\n* `void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s)`\n\n此函数会在 `aoi` 函数被调用之后且仅被调用一次。\n* 参数 $N$ 是 IOI 国 中的城市数量。\n* 参数 $M$ 是 IOI 国 中的道路数量。\n* 参数 $Q$ 是调查计划的数量。\n* 参数 $K$ 是 Bitaro 遗失长度信息的道路条数。\n* 参数 $A, B, C$ 为长度为 $M$ 的数组。表示第 $i$ 条道路（$0 \\le i \\le M-1$）双向连接城市 $A[i]$ 与城市 $B[i]$，长度为 $C[i]$。\n* 参数 $T$ 为长度为 $Q$ 的数组。表示第 $j$ 个计划（$0 \\le j \\le Q-1$）要调查的城市为 $T[j]$。\n* 参数 $X$ 为长度为 $K$ 的数组。表示 Bitaro 遗失长度信息的道路为 $X[0], X[1], \\dots, X[K-1]$。\n* 参数 $s$ 是一个每个字符均为 ‘0’ 或 ‘1’ 的字符串，表示 Aoi 发送给 Bitaro 的字符串。\n\n在 `Bitaro.cpp` 中，你的程序可以调用如下函数。\n\n```cpp\nvoid answer(const std::vector<int> &e)\n```\n\n* 在第 $(j+1)$ 次调用（$0 \\le j \\le Q-1$）该函数时，你需要回答从城市 $0$ 到第 $j$ 个调查计划目标城市 $T_j$ 的最短路径。\n* 参数 `e` 是一个数组，表示从城市 $0$ 到城市 $T_j$ 的最短路径所经过的道路序列。\n* 设数组 `e` 的长度为 $n$。元素 `e[0], e[1], \\ldots, e[n-1]` 是该最短路径上按行进顺序经过的道路的编号。\n* 若存在多条最短路径，任选其一作为答案即可。\n* 参数 `e` 的每个元素必须在 $0$ 到 $M-1$ 之间。若不满足此条件，你的程序将被判定为 **Wrong Answer [3]**。\n* 参数 `e` 所指示的道路序列必须构成一条从城市 $0$ 到城市 $T_j$ 的路径。更正式地，它必须满足以下条件。\n    * 存在一列数字 $u_0, u_1, \\ldots, u_n$ 使得\n        * $u_0 = 0$。\n        * $u_n = T_j$。\n        * 道路 $e[k]$（$0 \\le k \\le n-1$）连接城市 $u_k$ 与城市 $u_{k+1}$。\n    * 若不满足这些条件，你的程序将被判定为 **Wrong Answer [4]**。\n* 若参数 `e` 指示的道路序列并非所有从城市 $0$ 到城市 $T_j$ 的路径中长度最短的一条，你的程序将被判定为 **Wrong Answer [5]**。这里，路径长度定义为所用道路长度之和。\n* 函数 `answer` 必须被调用恰好 $Q$ 次。若在 `bitaro` 函数结束时，对 `answer` 的调用次数不等于 $Q$，你的程序将被判定为 **Wrong Answer [6]**。\n\n### 重要注意事项\n\n* 你的程序可以为内部使用实现其他函数，或使用全局变量。提交的文件将与评测程序一起编译，形成单个可执行文件。所有全局变量与内部函数应声明在未命名命名空间中，以避免与其他文件冲突。评测时会分别以 Aoi 进程与 Bitaro 进程运行。Aoi 进程与 Bitaro 进程不能共享全局变量。\n* 你的程序不得使用标准输入与标准输出。你的程序不得以任何方式与其他文件通信。但你可以向标准错误输出调试信息。\n\n### 编译与测试运行\n\n你可以从比赛网页下载包含样例评测器的压缩包，用于本地测试。压缩包中也包含你程序的样例源文件。\n\n样例评测器文件为 `grader.cpp`。为测试你的程序，请将 `grader.cpp`、`Aoi.cpp`、`Bitaro.cpp`、`Aoi.h`、`Bitaro.h` 放在同一目录下，并运行以下命令进行编译。你也可以运行压缩包内的 `compile.sh`。\n\n```bash\ng++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp\n```\n\n当编译成功时，将生成可执行文件 `grader`。\n\n注意，实际评测器不同于样例评测器。样例评测器作为单进程执行，从标准输入读取数据，并向标准输出与标准错误输出写出结果。\n\n## Input\n\n样例评测器从标准输入读取如下数据。\n\n> $N$ $M$\\\n> $A_0$ $B_0$ $C_0$\\\n> $A_1$ $B_1$ $C_1$\\\n> $A_{M-1}$ $B_{M-1}$ $C_{M-1}$\\\n> $Q$\\\n> $T_0$ $T_1$ $\\cdots$ $T_{Q-1}$\\\n> $K$\\\n> $X_0$ $X_1$ $\\cdots$ $X_{K-1}$\n\n## Output\n\n样例评测器向标准输出与标准错误输出输出如下信息（引号仅为说明）。\n\n* 若你的程序被判为 **Wrong Answer [1], [2], [3], [4], 或 [6]**，样例评测器会在标准错误输出写出其类型，如 “Wrong Answer [1]”。标准输出不会输出任何内容。\n* 否则，`aoi` 函数返回的字符串 $s$ 的长度会以 “Accepted: 2024” 的格式输出到标准错误输出。此外，在第 $(j+1)$ 次（$0 \\le j \\le Q-1$）对 `answer` 的调用中，路径长度会输出到标准输出的第 $(j+1)$ 行。样例评测程序 **不会检查** 该路径是否最短。\n\n若你的程序同时满足多种 Wrong Answer 的条件，样例评测器仅报告其中一种。\n\n[samples]\n\n## Background\n\n在本题中，你需要将两个文件合并成一个文件提交。\n\n**不要引入任何头文件**，并在文件头加入如下的内容：\n\n```cpp\n#include <vector>\nvoid answer(const std::vector<int> &);\n```\n\n## Note\n\n### 示例通信\n\n下面给出一个样例评测器的输入及相应的函数调用。\n\n| 样例输入 1 | 调用 | 返回值 |\n|---|---|---|\n| $$\\texttt{3 3}\\\\ \\texttt{1 2 1} \\\\ \\texttt{0 2 2} \\\\ \\texttt{0 1 3} \\\\ \\texttt{2} \\\\ \\texttt{2 1} \\\\ \\texttt{2} \\\\ \\texttt{0 1}$$ | `aoi(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [1, 2, 3], [2, 1], [0, 1])` |  |\n| ^ | | `\"101001\"` |\n| ^ | `bitaro(3, 3, 2, 2, [1, 0, 0], [2, 2, 1], [-1, -1, 3], [2, 1], [0, 1], \"101001\")` | |\n| ^ | `answer([1])` | |\n| ^ | `answer([1, 0])` | |\n\n从城市 $0$ 到城市 $1$ 的最短路径，可以按顺序经过道路 $1$ 和 $0$，或者仅经过道路 $2$。因此，在本样例的第二次对 `answer` 的调用中，调用 `answer([2])` 也是可以接受的。\n\n从比赛网站下载的文件 `sample-01-in.txt` 与输入样例 $1$ 相对应。压缩包中的 `sample-01-in.txt` 与 `sample-02-in.txt` 可作为样例评测器的输入。\n\n### 约束\n\n所有输入数据均满足以下条件：\n\n* $2 \\le N \\le 10000$。\n* $1 \\le M \\le 20000$。\n* $1 \\le Q \\le 16$。\n* $1 \\le K \\le 300$。\n* $0 \\le A_i < B_i \\le N-1$（$0 \\le i \\le M-1$）。\n* $(A_i, B_i) \\ne (A_j, B_j)$（$0 \\le i < j \\le M-1$）。\n* $1 \\le C_i \\le 10^{12}$（$0 \\le i \\le M-1$）。\n* $1 \\le T_j \\le N-1$（$0 \\le j \\le Q-1$）。\n* $T_j \\ne T_k$（$0 \\le j < k \\le Q-1$）。\n* $0 \\le X_k \\le M-1$（$0 \\le k \\le K-1$）。\n* $X_k \\ne X_l$（$0 \\le k < l \\le K-1$）。\n* 通过若干条道路可以在任意两座城市之间往来。\n* 所有输入值均为整数。\n\n### 评分\n\n若你的程序在任意测试用例中被判定为 **Wrong Answer [1] - [6]**（见实现细节）或出现任意类型的运行时错误（TLE、MLE、异常结束等），你的得分为 $0$ 分。\n\n否则，评分依据为在本题所有测试用例中，函数 `aoi` 返回的字符串 $s$ 的最大长度 $L$。\n\n* 若 $1561 \\le L \\le 12000$，得分为 $\\left\\lfloor \\dfrac{100\\,000}{L-560} \\right\\rfloor$。\n* 若 $0 \\le L \\le 1560$，得分为 $100$ 分。\n\n其中，$\\lfloor x \\rfloor$ 表示不超过 $x$ 的最大整数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10434","tags":["2024","交互题","Special Judge","最短路","虚树","Catalan 数","通信题","JOISC/JOIST（日本）"],"sample_group":[["3 3\n1 2 1\n0 2 2\n0 1 3\n2\n2 1\n2\n0 1",""]],"created_at":"2026-03-03 11:09:25"}}