P11988 [JOIST 2025] 宇宙怪盗 / Space Thief
题目背景
请使用 C++ 17 / C++ 20 提交。
**不要** `#include "thief.h"`。在文件头加入以下内容：
```cpp
#include
int query(std::vector);
void answer(int,int);
```
题目描述
**这是一道交互题。本题中，交互库可能是自适应的。**
有一张 $N$ 个点 $M$ 条边的无向连通图。点编号 $0\sim N-1$，边编号 $0\sim M-1$，第 $i$（$0 \leq i \leq M-1$）条边双向连接点 $U_i$ 和 $V_i$。
有一把钥匙藏在某一个点上，而有一个宝箱藏在另一个节点上。你需要通过至多 $300$ 次询问确定钥匙所在的节点编号和宝箱所在的节点编号：
> **询问**
>
> 对于 $i=0,1,\ldots,M-1$，将第 $i$ 条边设置为单向通行。
> - 具体地，构造长度为 $M$ 的 $01$ 序列 $x_0\sim x_{M-1}$。$x_i=0$ 表示第 $i$ 条边从 $U_i$ 指向 $V_i$，$x_i=1$ 表示第 $i$ 条边从 $V_i$ 指向 $U_i$。
>
> 交互库会返回，在这张图中，是否能从钥匙所在的节点到达宝箱所在的节点。
你需要确定钥匙所在的节点 $A$ 和宝箱所在的节点 $B$。为了获得更高的评分，你需要尽量减少询问次数。
### 实现细节
你不应该，也不需要实现 `main` 函数。你应该实现以下的函数：
```cpp
void solve(int N, int M, std::vector U, std::vector V)
```
- 该函数每组测试数据仅调用一次。
- 参数 `N` 是点数。
- 参数 `M` 是边数。
- 参数 `U`, `V` 是长度为 $M$ 的数组，表示边 $i$ 双向连接 $U_i$ 和 $V_i$。
你可以调用以下的函数：
```cpp
int query(std::vector x)
```
通过此函数，你可以发起一次询问。
- 参数 `x` 是一个长度为 $M$ 的数组。对于 $0 \leq i \leq M-1$：
- 若 `x[i] = 0`，表示仅允许从点 $U_i$ 到点 $V_i$ 的移动。
- 若 `x[i] = 1`，表示仅允许从点 $V_i$ 到点 $U_i$ 的移动。
- 返回值为 $0$ 或 $1$：
- $0$ 表示无法通过跃迁装置从钥匙所在的点 $A$ 到达宝箱所在的点 $B$。
- $1$ 表示可以到达。
- 参数 `x` 的长度必须为 $M$。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [1]}$。
- 参数 `x` 的每个元素必须是 $0$ 或 $1$。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [2]}$。
- 调用 `query` 函数的次数不得超过 $300$ 次。如果超过，你的程序将被判为 $\texttt{Wrong Answer [3]}$。
```cpp
void answer(int A, int B)
```
你需调用此函数来提交答案，即钥匙所在的点 $A$ 和宝箱所在的点 $B$。
- 参数 `A` 表示钥匙藏在点 $A$ 中。
- 参数 `A` 必须在 $0$ 到 $N-1$ 的范围内（两边取等）。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [4]}$。
- 参数 `B` 表示宝箱藏在点 $B$ 中。
- 参数 `B` 必须在 $0$ 到 $N-1$ 的范围内（两边取等）。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [5]}$。
- 如果提交的答案错误，你的程序将被判为 $\texttt{Wrong Answer [6]}$。
- `answer` 函数必须被**恰好调用一次**。如果多次调用，你的程序将被判为 $\texttt{Wrong Answer [7]}$。当 `solve` 函数终止时，如果未调用 `answer` 函数，你的程序将被判为 $\texttt{Wrong Answer [8]}$。
### 注意事项
- 你的程序可以定义其他函数或使用全局变量。
- 你的程序不得使用标准输入输出，也不得通过任何方式与其他文件通信。但允许将调试信息输出到标准错误流。
- 对于部分测试点，交互库是**自适应的**。这意味着交互库在开始时没有固定答案，而是根据之前对 `query` 函数的调用历史来响应。保证至少存在一个答案与交互库的所有回答不矛盾。
### 测试运行
你可以从附件中下载包含 Sample Grader 的压缩包。该压缩包还包含一个示例源文件。
Sample Grader 是文件 `grader.cpp`。
要测试你的程序，请将 `grader.cpp`、`thief.cpp`、`thief.h` 放在同一目录下，并运行以下命令进行编译：
```bash
g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp
```
或者，你可以运行压缩包中的 `compile.sh` 脚本。此时，使用以下命令进行编译：
```bash
./compile.sh
```
当编译成功时，会生成可执行文件 `grader`。注意，实际评测程序与Sample Grader 不同。Sample Grader 会作为单个进程运行，从标准输入读取数据并将结果写入标准输出。
输入格式
Sample Grader 输入格式如下所示：
> $N$ $M$ $A$ $B$\
> $U_0$ $V_0$\
> $U_1$ $V_1$\
> $\vdots$\
> $U_{M-1}$ $V_{M-1}$
输出格式
Sample Grader 输出格式如下：
- 如果你的程序被判为正确，会报告调用 `query` 函数的次数，例如 $\texttt{Accepted: 25}$。
- 如果你的程序被判为任何类型的错误答案，Sample Grader 会写出错误类型，例如$\texttt{Wrong Answer [4]}$。
如果你的程序满足多种错误类型的条件，Sample Grader 只会报告其中一种。当某一错误条件触发时，Sample Grader 可能直接终止执行。
说明/提示
### 样例交互
| 交互库调用 | 选手程序调用 | 返回值 |
| - | - | - |
|$\texttt{solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4])}$ |$ $ | |
| | $\texttt{query([0, 1, 0, 0])}$ | $1$ |
| | $\texttt{query([1, 1, 1, 0])}$ | $0$ |
| | $\texttt{query([0, 0, 1, 0])}$ | $1$ |
| | $\texttt{query([0, 0, 1, 1])}$ | $0$ |
| | $\texttt{answer(0, 4) }$ | |
- 第 $1$ 次调用 `query` 函数：
- 边 $ 0 $：仅允许从点 $ 0 $ 到点 $ 1 $。
- 边 $ 1 $：仅允许从点 $ 3 $ 到点 $ 0 $。
- 边 $ 2 $：仅允许从点 $ 1 $ 到点 $ 2 $。
- 边 $ 3 $：仅允许从点 $ 1 $ 到点 $ 4 $。
在此设置下，可以通过边 $0 \to 3$ 的顺序从点 $ 0 $ 到达点 $ 4 $，因此返回值为 $1$。
- 第 $2$ 次调用 `query` 函数：
- 边 $ 0 $：仅允许从点 $ 1 $ 到点 $ 0 $。
- 边 $ 1 $：仅允许从点 $ 3 $ 到点 $ 0 $。
- 边 $ 2 $：仅允许从点 $ 2 $ 到点 $ 1 $。
- 边 $ 3 $：仅允许从点 $ 1 $ 到点 $ 4 $。
在此设置下，无法从点 $ 0 $ 到达点 $ 4 $，因此返回值为 $0$。
- 第 $3$ 次调用 `query` 函数：
- 边 $ 0 $：仅允许从点 $ 0 $ 到点 $ 1 $。
- 边 $ 1 $：仅允许从点 $ 0 $ 到点 $ 3 $。
- 边 $ 2 $：仅允许从点 $ 2 $ 到点 $ 1 $。
- 边 $ 3 $：仅允许从点 $ 1 $ 到点 $ 4 $。
在此设置下，可以通过跃迁装置到达点 $ 4 $，因此返回值为 $1$。
- 第 $4$ 次调用 `query` 时，无法从点 $ 0 $ 到达 4，返回值为 $0$。
最终调用 `answer(0, 4)` 提交答案，表示钥匙在点 $ 0 $、宝箱在点 $ 4 $。
此样例输入满足子任务 $3\sim 8$ 的约束条件。竞赛网页提供的 `sample-01-in.txt` 文件对应此样例。
压缩包中的示例程序源码的函数调用与本示例一致。
### 数据范围
- $2 \leq N \leq 10\,000$；
- $1 \leq M \leq 15\,000$；
- $0 \leq A \leq N-1$；
- $0 \leq B \leq N-1$；
- $A \neq B$；
- $0 \leq U_i \lt V_i \leq N-1$（$0 \leq i \leq M-1$）；
- $(U_i, V_i) \neq (U_j, V_j)$（$0 \leq i \lt j \leq M-1$）；
- 可以通过跃迁装置从任意点到达其他任意点。
### 子任务 与 计分方式
- $\text{Subtask 1 (7 pts)}$：$M = N - 1$，且 $U_i = i,V_i = i + 1$（$0 \leq i \leq M - 1$）。
- $\text{Subtask 2 (13 pts)}$： $M = N - 1$，且 $U_i = 0,V_i = i + 1$（$0 \leq i \leq M - 1$）。
- $\text{Subtask 3 (2 pts)}$：$M = N - 1$，且 $N \leq 8$。
- $\text{Subtask 4 (8 pts)}$：$M = N - 1$，且 $N \leq 50$。
- $\text{Subtask 5 (5 pts)}$：$M = N - 1$，且 $N \leq 150$。
- $\text{Subtask 6 (5 pts)}$：$M = N - 1$，且 $N \leq 250$。
- $\text{Subtask 7 (40 pts)}$： $M = N - 1$。
在此子任务中，评分规则如下：
- 如果子任务 $7$ 中任意测试用例被判为 $\text{Wrong Answer}$，或运行超时、内存超限、运行错误，则该子任务得 $0$ 分。
- 否则，令 $T$ 表示本子任务所有测试用例中 `query` 函数调用次数的最大值。评分规则为：
- 若 $120 < T$，得 20 分。
- 若 $70 < T \leq 120$，得 30 分。
- 若 $T \leq 70$，得 40 分。
- $\text{Subtask 8 (20 pts)}$：无额外限制。
在此子任务中，评分规则如下：
- 如果子任务 $8$ 中任意测试用例被判为 $\text{Wrong Answer}$，或运行超时、内存超限、运行错误，则该子任务得 $0$ 分。
- 否则，令 $T$ 表示本子任务所有测试用例中 `query` 函数调用次数的最大值。评分规则为：
- 若 $120 < T$，得 10 分。
- 若 $70 < T \leq 120$，得 15 分。
- 若 $T \leq 70$，得 20 分。
子任务 $1\sim 6$ 的得分与 `query` 的调用次数无关（只要不超过 $300$ 次）。
对于部分测试点，交互库是**自适应的**。这意味着交互库在开始时没有固定答案，而是根据之前对 `query` 函数的调用历史来响应。保证至少存在一个答案与交互库的所有回答不矛盾。