P14414 [JOISC 2015] 导航 / Navigation【通信题暂无法评测】

安娜是 IOI 群岛的居民，她决定邀请朋友布鲁诺前往 IOI 群岛。IOI 群岛由编号从岛 1 到岛 $N$ 的 $N$ 个岛屿组成。此外，群岛中有 $N-1$ 座桥，桥的编号从 0 到 $N-2$。每座桥 $i$ 连接岛屿 $A_i$ 和 $B_i$，且为双向通行。所有岛屿之间均可通过桥梁相互到达。安娜的家位于岛屿 $T$，但布鲁诺并不知道安娜家所在岛屿的编号。 为了帮助布鲁诺，安娜在每个岛屿上竖立一面写有一个整数的旗帜。安娜不知道布鲁诺将抵达哪个岛屿。 布鲁诺乘船抵达岛屿 $S$。当他到达岛屿 $S$ 时，会获得以下信息： - 到达岛屿的编号 $S$，以及该岛屿旗帜上所写的整数 - 与岛屿 $S$ 直接相连的所有岛屿的编号，以及每个相连岛屿上旗帜所写的整数 布鲁诺从岛屿 $S$ 前往岛屿 $T$ 时，必须选择经过桥梁数量最少的路径。 问题是：布鲁诺能否仅根据自身获得的信息，判断自己所到达的岛屿 $S$ 是否就是安娜家所在的岛屿 $T$？如果 $S$ 与 $T$ 不同，他能否正确选择下一步前往的岛屿？ ### 题目 给定 IOI 群岛的信息，编写程序实现安娜在每个岛屿竖立写有整数旗帜的策略。同时，根据布鲁诺抵达岛屿时所获得的信息，编写程序实现布鲁诺能够正确选择下一步行动的策略。 ### 实现细节 你必须使用同一种编程语言提交两个文件。 第一个文件应命名为 `Anna.c` 或 `Anna.cpp`。该文件需实现安娜的策略，并包含以下函数： - `void Anna(int K, int N, int T, int A[], int B[])` 该函数将仅在开始时被调用一次。 - 参数 $K$ 表示子任务编号 $K$。 - 参数 $N$ 表示 IOI 群岛中岛屿的数量 $N$。 - 参数 $T$ 表示安娜家所在的岛屿编号 $T$。 - 参数 $A$ 和 $B$ 是长度为 $N-1$ 的数组。其中，元素 $A[i]$ 和 $B[i]$ 表示桥 $i$ 连接岛屿 $A[i]$ 和 $B[i]$（$0 \le i \le N-2$）。 此外，还需调用以下函数，在岛屿上竖立旗帜： - `void Flag(int I, int V)` - 参数 $I$ 表示安娜竖立旗帜的岛屿编号。 - 参数 $V$ 表示安娜写在旗帜上的整数。 但调用 `Flag` 必须满足以下条件： - $I$ 必须是 1 到 $N$ 之间的整数。若不满足，判定为 **Wrong Answer [1]**。 - 对于同一个索引 $I$，不能调用 `Flag` 两次或以上。若不满足，判定为 **Wrong Answer [2]**。 - $V$ 必须是 0 到 $N$ 之间的整数。若不满足，判定为 **Wrong Answer [3]**。 - `Flag` 必须被恰好调用 $N$ 次。若不满足，判定为 **Wrong Answer [4]**。 若 `Flag` 的调用被判定为错误，程序将立即终止。 第二个文件应命名为 `Bruno.c` 或 `Bruno.cpp`。该文件需实现布鲁诺的策略，并包含以下函数： - `void Bruno(int K, int S, int F, int L, int P[], int Q[])` 该函数在 `Anna` 被调用后，仅被调用一次。 - 参数 $K$ 表示子任务编号 $K$。 - 参数 $S$ 表示布鲁诺抵达的岛屿编号 $S$。 - 参数 $F$ 表示岛屿 $S$ 上旗帜所写的整数。 - 参数 $L$ 表示与岛屿 $S$ 直接相连的岛屿数量。 - 参数 $P$ 是长度为 $L$ 的数组，包含与岛屿 $S$ 直接相连的所有岛屿编号。 - 参数 $Q$ 是长度为 $L$ 的数组，其中元素 $Q[j]$ 表示在岛屿 $P[j]$ 上旗帜所写的整数（$0 \le j \le L-1$）。 此外，还需调用以下函数，以判断布鲁诺抵达的岛屿 $S$ 是否为安娜家所在的岛屿，若不是，则必须正确选择下一步前往的岛屿： - `void Answer(int X)` - 参数 $X$ 表示：若布鲁诺抵达的岛屿即为安娜家所在岛屿，则 $X$ 为安娜家所在岛屿的编号 $T$；否则，$X$ 为布鲁诺下一步应前往的岛屿编号。 但调用 `Answer` 必须满足以下条件： - 参数 $X$ 必须是数组 $P$ 中的某个元素，或等于 $S$。若不满足，判定为 **Wrong Answer [5]**。 - 若调用 **Answer** 两次或以上，判定为 **Wrong Answer [6]**。 - 若未调用 **Answer**，判定为 **Wrong Answer [7]**。 - 若岛屿 $S$ 上有安娜的家，但参数 $X$ 不等于 $T$，判定为 **Wrong Answer [8]**。 - 若岛屿 $S$ 上没有安娜的家，但参数 $X$ 不是下一步应前往的岛屿，判定为 **Wrong Answer [9]**。 在布鲁诺的函数被调用之后，将进行答案的判定。 在程序内部使用其他函数时，可以自由声明全局变量。但请注意，提交的两个程序将与评分程序一起链接，生成一个可执行文件。由于各文件中的全局变量和内部函数均以 `static` 声明，以避免相互干扰，因此在运行时，安娜侧和布鲁诺侧的程序将作为两个独立的进程执行，不能共享全局变量。 你提交的程序必须通过标准输入/标准输出，或通过其他文件等方式进行交互，不得使用其他方法。 ### 编译与运行方法 为测试所编写的程序，评分程序的样本可从竞赛网站下载，该样本包含一个归档文件，其中包含必要的文件，以及一些不需要提取的额外文件。 评分程序的样本由单个文件构成，该文件名为 `grader.c` 或 `grader.cpp`。 要测试编写的程序，请执行以下命令： - **C 语言情况：** ``` gcc -O2 -o grader grader.c Anna.c Bruno.c -lm ``` - **C++ 语言情况：** ``` g++ -std=c++11 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp ``` 若编译成功，将生成名为 `grader` 的可执行文件。 请注意，实际的评分程序与样本评分程序有所不同。样本评分程序以单个进程启动。该程序从标准输入读取数据，向标准输出输出结果。

从标准输入读取以下内容： - 第一行包含用空格分隔的整数 $N, S, T, K$，表示：IOI 群岛的岛屿数量为 $N$，布鲁诺抵达的岛屿编号为 $S$，安娜家所在的岛屿编号为 $T$，子任务编号为 $K$。 - 接下来的 $N-1$ 行中的第 $i+1$ 行（$0 \le i \le N-2$）包含用空格分隔的整数 $A_i, B_i$，表示桥 $i$ 双向连接岛屿 $A_i$ 和 $B_i$。 - 下一行包含一个整数 $Y$，表示该输入对应的答案。即，当 **Answer** 函数的参数 $X$ 为 $Y$ 时，评分程序样本判定为正确答案，否则判定为错误答案。

当程序正常执行完毕后，Grader 将向标准输出输出一行信息（实际运行中不会输出引用信息）： - 若正确：输出调用 **Flag** 函数时参数 $V$ 的最大值，格式如 “Accepted : V_max = 2”。 - 若错误：输出错误类型，格式如 “Wrong Answer [1]”。

### 函数调用示例 | Anna 侧 | Bruno 侧 | |:-------:|:--------:| | **Anna(...)** | | | **Flag(1,1)** | | | **Flag(2,1)** | | | **Flag(3,0)** | | | **Flag(4,0)** | | | **Flag(5,1)** | | | | **Bruno(...)** | | | **Answer(2)** | 请注意，本示例中的 **Flag** 调用未必具有实际意义。此时，传递给 **Anna(...)** 和 **Bruno(...)** 的参数如下所示： | 参数 | **Anna(...)** | |:----:|:--------------:| | $K$ | $1$ | | $N$ | $5$ | | $T$ | $2$ | | $A$ | $\{1, 3, 3, 4\}$ | | $B$ | $\{3, 2, 4, 5\}$ | | 参数 | **Bruno(...)** | |:----:|:--------------:| | $K$ | $1$ | | $S$ | $3$ | | $F$ | $0$ | | $P$ | $\{2, 1, 4\}$ | | $Q$ | $\{1, 1, 0\}$ | ### 数据范围 所有输入数据满足以下条件： - $2 \le N \le 100\,000$ - $1 \le S \le N$ - $1 \le T \le N$ - $1 \le A_i \le N$（$0 \le i \le N-2$） - $1 \le B_i \le N$（$0 \le i \le N-2$） - $1 \le K \le 4$ - IOI 群岛中，从任意岛屿出发，均可通过桥梁到达所有其他岛屿。 ### 子任务 #### 子任务 1 [10 分] - 满足 $K = 1$ #### 子任务 2 [15 分] - 满足 $K = 2$ - 传递给 **Flag** 函数的参数 $V$ 的值必须在 0 到 2 之间（含端点）。 #### 子任务 3 [20 分] - 满足 $K = 3$ - 传递给 **Flag** 函数的参数 $V$ 的值必须为 0 或 1。 - 不存在与恰好两个岛屿直接相连的岛屿。 - 满足 $S \ne T$ #### 子任务 4 [55 分] - 满足 $K = 4$ - 传递给 **Flag** 函数的参数 $V$ 的值必须为 0 或 1。