P14390 [JOISC 2017] 自然公园 / Natural Park

JOI 岛是一个观光区，整座岛屿被指定为自然公园。 JOI 岛上有 $N$ 个地点和若干条道路。这些地点从 $0$ 到 $N-1$ 编号。每条道路连接两个不同的地点，且可双向通行。每个地点最多连接 7 条道路。任意两个不同地点之间至多仅有一条道路相连。只要经过若干条道路，我们便可从任意地点到达其他任意地点。 你和你的朋友 IOI 女士将共同调查 JOI 岛。为高效完成调查，你需要弄清 JOI 岛的结构。JOI 岛十分危险，因为岛上栖息着许多野生动物。由于 IOI 女士拥有出色的运动能力，她将负责实地探索 JOI 岛，而你则根据 IOI 女士的报告来确定 JOI 岛的结构。 你将提供两个地点 $A$、$B$ 以及若干中间地点给 IOI 女士，并询问：若仅允许经过给定的中间地点，是否可能从地点 $A$ 到达地点 $B$？随后，IOI 女士将探索 JOI 岛，并将结果报告给你。 由于调查时间不能过长，查询次数应小于或等于 45000。 **任务** 编写一个程序，与 IOI 女士通信并确定 JOI 岛的结构。 **实现细节** 你需要编写一个程序，实现确定 JOI 岛结构的方法。你的程序应当声明函数 `void Answer(int A, int B);` 和 `int Ask(int A, int B, int Place[]);`，并且使用不低于 C++17 的语言标准提交试题。 你的程序应实现以下函数： - `void Detect(int T, int N)` 该函数仅被调用一次。 - 参数 $T$ 为子任务编号，$N$ 为地点数量。 你的程序应通过调用以下函数，输出其确定的 JOI 岛结构： - `void Answer(int A, int B)` 调用该函数的次数应等于 JOI 岛中道路的总数。 - 参数 $A$、$B$ 表示存在一条连接地点 $A$ 与地点 $B$ 的道路。 参数应满足以下条件： - $A$、$B$ 应满足 $0 \le A < B \le N-1$。若此条件不满足，你的程序将被判定为 **Wrong Answer[1]**。 - 若函数以参数 $(A, B)$ 被调用，则必须存在一条连接地点 $A$ 与地点 $B$ 的道路。若此条件不满足，你的程序将被判定为 **Wrong Answer[2]**。 - 函数不应以相同的参数 $(A, B)$ 被调用超过一次。若此条件不满足，你的程序将被判定为 **Wrong Answer[3]**。 此外，你的程序可调用以下函数： - `int Ask(int A, int B, int Place[])` 该函数用于向 IOI 女士提问。 - `Place` 是一个数组的指针，表示可能经过的中间地点。对于每个 $i$（$0 \le i \le N-1$），若 `Place[i] = 1`，表示可经过地点 $i$；若 `Place[i] = 0`，表示不可经过地点 $i$。 - 若仅允许经过数组 `Place[]` 中指定的某些地点，可以从地点 $A$ 到达地点 $B$，则该函数返回值为 1；否则返回值为 0。 参数应满足以下条件： - $0 \le A < B \le N-1$。 - $0 \le \text{Place}[i] \le 1$（$0 \le i \le N-1$）。 - $\text{Place}[A] = 1$。 - $\text{Place}[B] = 1$。 若上述条件未被满足，你的程序将被判定为 **Wrong Answer[4]**。然而，若数组 `Place[]` 的长度不等于 $N$，该函数的行为无法保证。 函数 `Ask` 的调用次数不得超过 45000 次。若超出，你的程序将被判定为 **Wrong Answer[5]**。 当函数 `Detect` 执行完毕后，若存在某条道路未作为先前对函数 `Answer` 的调用参数出现，则你的程序将被判定为 **Wrong Answer[6]**。 你的程序可实现其他函数供内部使用，或使用全局变量。你的程序不得使用标准输入和标准输出，也不得通过任何方式与其他文件通信。 **编译与测试运行** 你可以从竞赛网页下载一个归档文件，其中包含一个用于测试你程序的示例评测程序。该归档文件还包含你的程序的一个示例源代码文件。 一个示例评测程序由一个源文件组成，该文件名为 `grader.c` 或 `grader.cpp`。例如，如果你的程序名为 `park.c` 或 `park.cpp`，你可以运行以下命令来编译你的程序。 - C `gcc -std=c11 -O2 -o grader grader.c park.c -lm` - C++ `g++ -std=c++14 -O2 -o grader grader.cpp park.cpp` 当编译成功后，将生成可执行文件 `grader`。 请注意，实际的评测程序与示例评测程序不同。示例评测程序将以单个进程运行，从标准输入读取输入数据，并将结果写入标准输出。

示例评测程序从标准输入读取以下数据： - 第一行输入包含一个整数 $T$，表示子任务编号。 - 第二行输入包含一个整数 $N$，表示地点数量。 - 第三行输入包含一个整数 $M$，表示道路数量。 - 在接下来的 $M$ 行中，第 $i$ 行（$1 \le i \le M$）包含两个以空格分隔的整数 $A_i$、$B_i$。这表示存在一条连接地点 $A_i$ 与地点 $B_i$ 的道路，且该道路可双向通行。

当程序成功终止时，示例评测程序将向标准输出写入以下信息。（引号实际不会输出。） - 若你的程序被视为正确，示例评测程序将输出 “Accepted.”。 - 若你的程序被视为 **Wrong Answer**，示例评测程序将按以下格式输出其类型：“Wrong Answer [1]”，随后你的程序将被终止。 若你的程序被视为多种类型的 **Wrong Answer**，示例评测程序仅报告其中一种。

### 示例调用 | 调用 | 返回值 | |:----:|:------:| | `Ask(3, 5, {0,0,1,1,1,1})` | 1 | | `Answer(2, 4)` | | | `Answer(2, 5)` | | | `Answer(3, 4)` | | | `Ask(0, 4, {1,0,1,0,1,0})` | 0 | | `Answer(0, 1)` | | | `Answer(0, 3)` | | | `Answer(1, 4)` | | | `Answer(1, 2)` | | 请注意，本示例中的函数调用不一定具有实际意义。在本示例中，函数 `Detect` 以参数 $T = 1$、$N = 6$ 被调用。在本示例中，JOI 岛屿的结构如下： :::align{center}  JOI 岛屿的结构。 圆圈和数字表示地点及其编号，线段表示道路。 ::: - 第一次调用函数 `Ask` 是询问：若仅允许经过地点 2、3、4、5，是否可以从地点 3 到达地点 5。由于可行，函数 `Ask` 返回 1。 - 第二次调用函数 `Ask` 是询问：若仅允许经过地点 0、2、4，是否可以从地点 0 到达地点 4。由于不可行，函数 `Ask` 返回 0。 ### 约束条件 所有输入数据均满足以下条件。关于 $T$、$N$、$M$ 的含义，请参见“示例评测程序的输入”。 - $1 \le T \le 5$。 - $2 \le N \le 1400$。 - $1 \le M \le 1500$。 - 对于每个地点，最多有 7 条道路连接它与其他地点。 - 若允许经过若干条道路，则可以从任意地点到达其他任意地点。 - 对于任意两个不同的地点，最多只有一条道路连接它们。 ### 子任务 共有 5 个子任务。每个子任务的得分及附加约束如下： **子任务 1 [10 分]** - $T = 1$。 - $N \le 250$。 **子任务 2 [10 分]** - $T = 2$。 - $M = N - 1$。 - 对于地点 0 或 $N-1$，恰好有一条道路连接它与其他地点；对于其他每个地点，恰好有两条道路连接它与其他地点。 **子任务 3 [27 分]** - $T = 3$。 - $M = N - 1$。 - 对于每个 $i$（$1 \le i \le N - 1$），若我们最多经过 8 个其他地点，则可以从地点 0 到达地点 $i$。 **子任务 4 [30 分]** - $T = 4$。 - $M = N - 1$。 **子任务 5 [23 分]** - $T = 5$。 翻译由 Qwen3-235B 完成