P9524 [JOIST 2022] 飞机旅行 / Flights

请使用 C++ 20 提交。 **不要**引入头文件，并在文件头加入以下内容： ```cpp void SetID(int, int); ```

在 JOI 共和国中，有 $N$ 个机场，编号从 $0$ 到 $N - 1$。有 $N - 1$ 条航线，编号从 $0$ 到 $N - 2$。航线 $i$（$0 \le i \le N - 2$）双向连接机场 $U_i$ 与机场 $V_i$。通过若干条航线相连，可以从任意一个机场到达任意另一个机场。对每个机场，连接它与其他机场的航线数量至多为 $3$。 Benjamin 计划在 JOI 共和国旅行。在旅程的最后一天，他想到达温泉所在的机场。游乐园位于机场 $x$，温泉位于机场 $y$。由于 Benjamin 对航线一无所知，他将与航空公司的工作人员 Ali 沟通。Benjamin 想知道：从游乐园所在的机场出发，到达温泉所在的机场，最少需要乘坐多少条航线。Ali 掌握航线信息，但 Benjamin 并不知道自己应当乘坐哪些航线。 1. Ali 为每个机场设置一个 **ID 码**。ID 码是介于 $0$ 和 $2N + 19$（含）之间的整数。 2. Benjamin 得到游乐园所在机场的 ID 码 $X$，以及温泉所在机场的 ID 码 $Y$。 3. Benjamin 向 Ali 发送一封电子邮件。该邮件是一串长度 **恰好** 等于 $20$ 的字符串，字符串的每个字符均为 $0$ 或 $1$。 4. Ali 给 Benjamin 回一封信。该信是一串长度在 $1$ 到 $300\,000$（含）之间的字符串，字符串的每个字符均为 $0$ 或 $1$。 请编写程序，实现航空公司工作人员 Ali 与旅客 Benjamin 的策略。注意：在第 $2$ 步中，Benjamin 能得到游乐园与温泉所在机场的 ID 码 $X, Y$，**然而 Benjamin 不能获得机场编号 $x, y$**。  ### 实现细节 你需要提交两个文件。 #### `Ali.cpp` 该文件应实现 Ali 的策略，并实现下述两个函数。程序应使用预处理指令 `#include` 引入 `Ali.h`。 - `void Init(int N, std::vector U, std::vector V)` 该函数用于为每个机场设置 ID 码（见「评分」中的场景说明），每个场景调用 **恰好一次**。 - 参数 $N$ 为 JOI 共和国中的机场数量。 - 参数 $U, V$ 为长度为 $N - 1$ 的数组，即 $U[i], V[i]$ 分别是航线 $i$（$0 \le i \le N - 2$）连接的机场 $U_i, V_i$。 - `std::string SendA(std::string S)` 该函数实现 Ali 给 Benjamin 的回信策略（见「评分」中的场景说明），在调用 `SendB`（见下文）之后、每个场景调用 **恰好一次**。 - 参数 $S$ 是长度为 $20$ 的字符串，即 Benjamin 发给 Ali 的电子邮件。 - 函数 `SendA` 应返回一个字符串，即 Ali 给 Benjamin 的回信。 - 返回值的长度必须在 $1$ 到 $300\,000$（含）之间。若不满足，则判为 **Wrong Answer [5]**。 - 返回值的每个字符必须为 $0$ 或 $1$。若不满足，则判为 **Wrong Answer [6]**。 对每次调用 `Init`，下述函数必须对每个机场调用一次，总计调用 $N$ 次： - `void SetID(int p, int value)` - 参数 $p$ 表示为机场 $p$ 设置 ID 码。必须满足 $0 \le p \le N - 1$。若不满足，则判为 **Wrong Answer [1]**。 - 参数 `value` 是 Ali 指定的该机场的 ID 码。必须满足 $0 \le value \le 2N + 19$。若不满足，则判为 **Wrong Answer [2]**。 - 不允许对同一个 $p$ 调用多次 `SetID`。若不满足，则判为 **Wrong Answer [3]**。 - 当 `Init` 结束时，`SetID` 的调用次数应为 $N$。若不满足，则判为 **Wrong Answer [4]**。 一旦某次 `SetID` 调用被判为 Wrong Answer，程序将立即终止。 #### `Benjamin.cpp` 该文件应实现 Benjamin 的策略，并实现下述两个函数。程序应使用预处理指令 `#include` 引入 `Benjamin.h`。 - `std::string SendB(int N, int X, int Y)` 该函数实现 Benjamin 发给 Ali 的电子邮件策略（见「评分」中的场景说明），在 `Init` 调用之后、每个场景调用 **恰好一次**。 - 参数 $N$ 为 JOI 共和国中的机场数量。 - 参数 $X$ 为游乐园所在机场的 ID 码。 - 参数 $Y$ 为温泉所在机场的 ID 码。 - 函数 `SendB` 应返回 Benjamin 发给 Ali 的邮件字符串。 - 若返回值不是长度为 $20$ 的字符串，则判为 **Wrong Answer [7]**。 - 若返回值的任一字符不是 $0$ 或 $1$，则判为 **Wrong Answer [8]**。 - `int Answer(std::string T)` 该函数应计算从机场 $x$ 到机场 $y$ 的最少乘坐航线数（见「评分」中的场景说明），在 `SendA` 调用之后、每个场景调用 **恰好一次**。 - 参数 $T$ 为 Ali 发给 Benjamin 的回信字符串，长度在 $1$ 到 $300\,000$（含）之间。 - 函数应返回从机场 $x$ 到机场 $y$ 所需的最少航线数量。 ### 重要注意事项 - 程序可以实现其他内部使用的函数，或使用全局变量。提交的文件将与评测器一同编译，组成单个可执行文件。为避免与其他文件冲突，所有全局变量与内部函数都应声明在匿名命名空间中。评测时将分别作为 Ali 与 Benjamin 两个进程执行。Ali 进程与 Benjamin 进程 **不能共享** 全局变量。 - 程序 **不得** 使用标准输入与标准输出。程序 **不得** 通过任何方式与其他文件通信。但你可以向标准错误输出调试信息。 ### 评分 一个测试用例由 $Q$ 个场景组成，编号为 $0$ 到 $Q - 1$。每个场景给定如下数据（取值范围见「约束」）： - JOI 共和国的机场数量 $N$。 - 游乐园所在的机场编号 $x$。 - 温泉所在的机场编号 $y$。 - 航线信息 $(U_0, V_0), (U_1, V_1), \dots, (U_{N - 2}, V_{N - 2})$。 对每个场景，依次调用 `Init`、`SendB`、`SendA`、`Answer`。你的程序应在这些调用中使用合法参数并返回合法值。调用顺序如下： 1. 对 $k = 0, 1, \dots, Q - 1$，依次执行步骤 $2$–$5$。 2. 调用 `Init`，参数按场景 $k$ 的「实现细节」说明设置。 3. 调用 `SendB`，参数按场景 $k$ 的「实现细节」说明设置。 4. 调用 `SendA`，参数按场景 $k$ 的「实现细节」说明设置。 5. 调用 `Answer`，参数按场景 $k$ 的「实现细节」说明设置。 若程序在这些过程中任一处被判为 Wrong Answer，程序将立即终止，并视为未通过该测试用例。  ### 编译与本地测试 你可以从竞赛网页下载包含样例评测器的压缩包，用于本地测试。压缩包中也包含你程序的样例源文件。 样例评测器文件名为 `grader.cpp`。为测试你的程序，请将 `grader.cpp`、`Ali.cpp`、`Benjamin.cpp`、`Ali.h`、`Benjamin.h` 放在同一目录下，并运行以下命令进行编译： ``` g++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp ``` 若编译成功，将生成可执行文件 `grader`。 注意：实际评测器与样例评测器不同。样例评测器作为单进程执行，从标准输入读取数据并向标准输出写出结果。

样例评测器从标准输入读取如下数据。所有输入值均为整数。 > $Q$ >（场景 $0$ 的输入） >（场景 $1$ 的输入） >$\vdots$ >（场景 $Q - 1$ 的输入） 每个场景的输入格式如下： > $N$ $x$ $y$ > $U_0$ $V_0$ > $U_1$ $V_1$ >$\vdots$ > $U_{N - 2}$ $V_{N - 2}$

如果程序被判为 Wrong Answer [1]–[8] 中的任意一种，样例评测器会输出其类型（引号仅为说明）：“Wrong Answer [1]”。 否则，对每个场景，它会输出函数 `Answer` 的返回值以及 Ali 发给 Benjamin 的字符串的最大长度。样例评测器 **不会** 检查 `Answer` 的返回值是否正确。 ``` Scenario 0: Your Answer = 3 Scenario 1: Your Answer = 1 Scenario 2: Your Answer = 4 Scenario 3: Your Answer = 1 Scenario 4: Your Answer = 5 Accepted: Maximum Length = 24 ``` 如果你的程序同时满足多种 Wrong Answer 的判定条件，样例评测器只报告其中一种。此外，即使你的程序在后续场景被判为 Wrong Answer [1]–[8]，只要在第一个场景未被判错，样例评测器也可能先输出如下中间结果： ``` Scenario 0: Your Answer = 3 Scenario 1: Your Answer = 1 Scenario 2: Your Answer = 4 Wrong Answer [8] ```

#### 约束 - $1 \le Q \le 50$。 - $2 \le N \le 10\,000$。 - $0 \le U_i < V_i \le N - 1$（$0 \le i \le N - 2$）。 - $0 \le x \le N - 1$。 - $0 \le y \le N - 1$。 - $x \ne y$。 - 通过若干条航线相连，可以从任意一个机场到达任意另一个机场。 - 对每个机场，连接它与其他机场的航线数量至多为 $3$。 #### 子任务 1.（$15$ 分）$Q = 1$。 2.（$85$ 分）$Q \ge 2$。 #### 子任务 1 的评分 若你的程序在子任务 $1$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。 若你的程序正确回答子任务 $1$ 的所有测试用例，得分按下述规则计算。设 $L_1$ 为 Ali 发给 Benjamin 的字符串的最大长度。 | $L_1$ 的取值 | 得分 | | :--- | :--- | | $150\,001 \le L_1 \le 300\,000$ | $7$ 分 | | $20\,001 \le L_1 \le 150\,000$ | $11$ 分 | | $L_1 \le 20\,000$ | $15$ 分 | #### 子任务 2 的评分 若你的程序在子任务 $2$ 的任意场景中被判为 Wrong Answer，则该子任务得分为 $0$。 若你的程序正确回答子任务 $2$ 的所有测试用例，得分按下述规则计算。设 $L_2$ 为 Ali 发给 Benjamin 的字符串的最大长度。**注意：若 $1\,401 \le L_2$，该子任务得分为 $0$。** | $L_2$ 的取值 | 得分 | | :--- | :--- | | $1\,401 \le L_2 \le 300\,000$ | $0$ 分 | | $71 \le L_2 \le 1\,400$ | $52 - 35 \times \log_{10}\!\bigl(\frac{L_2}{70}\bigr)$ 分（向下取整） | | $45 \le L_2 \le 70$ | $87 - 0.5 \times L_2$ 分（向下取整） | | $25 \le L_2 \le 44$ | $109 - L_2$ 分 | | $L_2 \le 24$ | $85$ 分 | ### 样例交互 以下为样例评测器的样例输入与对应的函数调用。在该示例中，Ali 在 `Init` 中为机场 $0, 1, 2, 3$ 设置的 ID 码分别为 $12, 21, 25, 27$。 #### 样例输入 1 | Ali 的调用 | Ali 的返回值 | Benjamin 的调用 | Benjamin 的返回值 | | :--- | :--- | :--- | :--- | | $\texttt{Init(4,[0,1,2],[1,2,3])}$ | | | | | $\texttt{SetID(0,12)}$ | | | | | $\texttt{SetID(1,21)}$ | | | | | $\texttt{SetID(2,25)}$ | | | | | $\texttt{SetID(3,27)}$ | | | | | | | $\texttt{SendB(12,25)}$ | $\texttt{"0000011111000011111"}$ | | $\texttt{SendA("00...11")}$ | $\texttt{"10"}$ | | | | | | $\texttt{Answer("10")}$ | $\texttt{2}$ | 在该样例中，有 $N (= 4)$ 个机场与三条航线： - 一条连接机场 $0$ 与机场 $1$ 的航线； - 一条连接机场 $1$ 与机场 $2$ 的航线； - 一条连接机场 $2$ 与机场 $3$ 的航线。 从机场 $x (= 0)$ 到机场 $y (= 2)$ 至少需要乘坐 $2$ 条航线，因此 `Answer` 应返回 $2$。 注意：`SendB` 的返回值并不是机场编号 $(x, y) = (0, 2)$，而是机场的 ID 码 $(X, Y) = (12, 25)$。 #### 样例输入 2 ``` 2 10 0 9 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 15 12 8 0 1 0 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 6 14 ``` 在该样例中，$Q = 2$ 个场景： - 对于第一个场景，`Answer` 应返回 $9$。 - 对于第二个场景，`Answer` 应返回 $6$。