#5049. 「JOISC 2025 Day2」宇宙怪盗

题目译自 JOISC 2025 Day2 T3 「宇宙怪盗 / Space Thief」

题目描述

在 JOI 银河中，你是一位声名赫赫的怪盗。JOI 银河拥有 $N$ 个星球，编号从 $0$ 到 $N-1$，还有 $M$ 个传送装置，编号从 $0$ 到 $M-1$。每个传送装置 $i$ ($0 \leq i \leq M-1$) 双向连接星球 $U_i$ 和 $V_i$，且任意两颗星球间都能通过若干传送装置到达。

某颗星球藏着一把钥匙，另一颗藏着宝箱。你的任务是找出钥匙所在的星球编号 $A$ 和宝箱所在的星球编号 $B$。为此，你最多可以进行 $300$ 次提问：

• 对每个传送装置 $i$ ($0 \leq i \leq M-1$)，选择将其改为单向连接：从 $U_i$ 到 $V_i$，或从 $V_i$ 到 $U_i$。
• 然后询问在此设定下，是否能从钥匙星球 $A$ 通过若干传送装置到达宝箱星球 $B$。

你希望通过提问锁定 $A$ 和 $B$，并为了赢得高评价，尽量减少提问次数。给定银河的信息，编写一个程序实现你的策略，找出钥匙和宝箱的位置。

实现细节

你需提交一个名为 thief.cpp 的文件。该文件需通过 #include 引入 thief.h，并实现以下函数：

void solve(int N, int M, std::vector<int> U, std::vector<int> V)

每个测试点调用一次。

• 参数 $N$ 是星球数量 $N$。
• 参数 $M$ 是传送装置数量 $M$。
• 参数 $U,V$ 是长度为 $M$ 的数组，$U[i]$ 和 $V[i]$ 表示传送装置 $i$ 双向连接的星球编号 $U_i$ 和 $V_i$。

在 thief.cpp 中可调用以下函数：

int query(std::vector<int> x)

用于提问。

• 参数 $x$ 是长度为 $M$ 的数组，对于 $0 \leq i \leq M-1$，$x[i]$ 为 $0$ 表示装置 $i$ 从 $U_i$ 到 $V_i$ 单向连接，$x[i]$ 为 $1$ 表示从 $V_i$ 到 $U_i$ 单向连接。
• 返回值为 $0$ 表示无法从 $A$ 到 $B$，$1$ 表示可行。

约束：

• $x$ 长度必须为 $M$，否则判为 Wrong Answer [1]。
• $x$ 各元素须为 $0$ 或 $1$，否则判为 Wrong Answer [2]。
• 调用次数不得超 $300$，否则判为 Wrong Answer [3]。

void answer(int A, int B)

提交答案。

• 参数 $A$ 是钥匙星球编号，需满足 $0 \leq A \leq N-1$，否则判为 Wrong Answer [4]。
• 参数 $B$ 是宝箱星球编号，需满足 $0 \leq B \leq N-1$，否则判为 Wrong Answer [5]。
• 若 $A$ 或 $B$ 错误，判为 Wrong Answer [6]。
• 必须调用恰好一次，多于一次判为 Wrong Answer [7]，未调用判为 Wrong Answer [8]。

注意事项

• 可自由定义其他函数或全局变量。
• 程序不得与标准输入输出或其他文件交互，但可输出调试信息到标准错误流。
• 部分测试点为自适应评测，即答案非固定，随 query 调用动态调整，但保证存在至少一种一致解。

样例

输入

5 4 0 4
0 1
0 3
1 2
1 4

函数调用

solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4])	
query([0, 1, 0, 0])	1
query([1, 1, 1, 0])	0
query([0, 0, 1, 0])	1
query([0, 0, 1, 1])	0
answer(0, 4)	

解释

第 1 次 query 函数调用的选择如下：

• 传送装置 0：从星球 0 到星球 1 单向连接。
• 传送装置 1：从星球 3 到星球 0 单向连接。
• 传送装置 2：从星球 1 到星球 2 单向连接。
• 传送装置 3：从星球 1 到星球 4 单向连接。

在此设置下，可以通过传送装置 0, 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 单向连接。

在此设置下，可以通过传送装置从星球 0 移动到星球 4，因此返回值为 1。

第 4 次 query 函数调用的选择下，无法通过传送装置从星球 0 移动到星球 4，因此返回值为 0。

answer 函数调用表示回答藏有钥匙的星球为 0，藏有宝箱的星球为 4。

此样例满足子任务 $3,4,5,6,7,8$ 的限制，对应 sample-01-in.txt。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10000$
• $1 \leq M \leq 15000$
• $0 \leq A \leq N-1$
• $0 \leq B \leq N-1$
• $A \neq B$
• $0 \leq U_i < V_i \leq N-1$ ($0 \leq i \leq M-1$)
• $(U_i, V_i) \neq (U_j, V_j)$ ($0 \leq i < j \leq M-1$)
• 任意两星球间可通过若干传送装置连通

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	7	$M = N-1$, $U_i = i$, $V_i = i+1$ ($0 \leq i \leq M-1$)
2	13	$M = N-1$, $U_i = 0$, $V_i = i+1$ ($0 \leq i \leq M-1$)
3	2	$M = N-1$, $N \leq 8$
4	8	$M = N-1$, $N \leq 50$
5	5	$M = N-1$, $N \leq 150$
6		$M = N-1$, $N \leq 250$
7	40	$M = N-1$，得分根据 $T$（query 最大调用次数）：$T > 120$ 得 20 分，$70 < T \leq 120$ 得 30 分，$T \leq 70$ 得 40 分，任一测试点错误得 0 分
8	20	无附加限制，得分根据 $T$：$T > 120$ 得 10 分，$70 < T \leq 120$ 得 15 分，$T \leq 70$ 得 20 分，任一测试点错误得 0 分

子任务 1 至 6 得分不根据 query 次数（$\leq 300$ 即可），但超 70 次可能显示 Partially Correct。