[IATI2018 day2]Park
Park（公园）
题目描述
Vasi 终于决定去鲁塞（Ruse）旅游，并在当地的公园里散步。她从导游那里得知，这座公园是一个长方形，它的两条长边长度都是 N。在这两条长边上，各有 N+1 个有趣的地点（咖啡馆、网球场、喷泉等等），因此一共有 2N+2 个地点。
这些地点按题图方式编号并通过小路连接。公园只有一个入口——编号为 1 的地点；也只有一个出口——编号为 2N+2 的地点。
所有小路都是单向的，散步时必须遵守它们的方向。小路方向满足以下条件：
- 整张图中不存在有向环；
- 入口是唯一一个所有相邻小路都从这里出发的点；
- 出口是唯一一个所有相邻小路都指向这里的点；
- 对于其他所有点，既有入边也有出边。
如果一条小路的方向是从编号较小的地点指向编号较大的地点，我们称它的方向为正方向，记作 1；否则称为负方向，记作 0。
Vasi 已经知道：
- 从入口出发的两条小路一定是正方向；
- 通向出口的两条小路也一定是正方向。
但是，其余小路的方向她并不知道。为了规划路线，她想要弄清楚所有小路的方向。
公园入口处有一台计算机，可以回答一种奇怪的询问：
给出若干条小路（用它们连接的两个地点编号表示），程序会返回这些小路方向值的**异或（XOR）**结果。
其中：
- 正方向记为
1； - 负方向记为
0； - 如果只询问一条小路，那么返回值就是该小路本身的方向。
Vasi 希望在不询问太多次的前提下，确定所有小路的方向。
评测程序已经把这台计算机模拟出来了。你需要编写函数 run，通过调用给定接口进行询问，并最终汇报每一条小路的方向。
实现要求
这是一道提交函数题。
你需要实现如下函数：
void run(int n);
该函数只会被调用一次，其中参数 n 就是题目中的 N。
你提交的文件名应为：
park.cpp
并且文件开头必须包含：
#include "park.h"
你的代码中不能包含 main 函数。
交互接口
你可以调用评测器提供的如下两个函数：
bool get_xor(const std::vector<std::pair<int, int>>& edges);
void state_direction(const std::pair<int, int>& edge, bool direction);
get_xor
- 返回参数
edges中所有小路方向值的异或结果； - 每条小路用一对整数表示，即它连接的两个地点编号，二者顺序可以任意；
- 该函数的时间复杂度和空间复杂度都与询问中的边数成线性关系。
state_direction
- 用于向评测器声明某一条小路的真实方向；
- 参数
edge表示一条小路； - 参数
direction表示你认定的方向：1：正方向（小编号指向大编号）；0：负方向（大编号指向小编号）。
评测规则
如果出现以下任意情况，该测试点得分为 0：
- 你向
get_xor或state_direction传入了不存在的小路； - 你向
state_direction声明了错误的方向； - 程序结束时，仍有某些小路没有被声明方向。
约束条件
1 \le N \le 100000
评分标准
记 Q 为单个测试点中调用 get_xor 的次数。
你的程序只有在每个测试点都在时限内完成，且满足 Q \le 3N 时，才能得到非零分。
具体评分如下：
15分：所有测试均满足Q \le 3N，但至少存在一个测试满足Q > 2N；45分：所有测试均满足Q \le 2N，但至少存在一个测试满足Q > \left\lceil \frac{3N}{2} \right\rceil；70分：所有测试均满足Q \le \left\lceil \frac{3N}{2} \right\rceil，但至少存在一个测试满足Q > \left\lceil \frac{16N}{11} \right\rceil；100分：所有测试均满足Q \le \left\lceil \frac{16N}{11} \right\rceil。
本地测试
题目提供了文件 Lgrader.cpp，你可以把它与自己的程序一起编译运行。
运行后，它会先询问 N，然后依次询问所有小路的方向（输入 0 或 1），并打印出双方通信过程。
你可以根据需要自行修改该文件。
关于系统测试与自适应数据
在某些你不知道的测试点上，评测器会采用自适应方式回答你的询问。也就是说，公园中小路的具体方向可能会随着你发出的询问不同而不同，只要始终满足题目给定条件即可。
普通提交时，你无法看到这种自适应机制的内部过程。
系统测试输入格式（供评测器内部使用）如下：
- 一个正整数
N； - 接下来是
4N+1个0/1，依次表示所有小路的方向。
这些小路按如下顺序给出：
(1,2), (1,3), (2,3), (2,4), ..., (k,k+1), (k,k+2), ...
样例通信
评测器调用
run(2)
通信过程
| 步骤 | run 的操作 |
评测器的回答 |
|---|---|---|
| 1 | run(2) |
|
| 2 | state_direction({1,2}, 1) |
|
| 3 | state_direction({1,3}, 1) |
|
| 4 | state_direction({4,6}, 1) |
|
| 5 | state_direction({5,6}, 1) |
|
| 6 | get_xor({{3,4},{3,5},{4,5}}) |
1 |
| 7 | get_xor({{3,5}}) |
|
| 8 | state_direction({3,4}, 1) |
|
| 9 | state_direction({3,5}, 1) |
|
| 10 | state_direction({4,5}, 1) |
|
| 11 | get_xor({{2,3},{2,4}}) |
0 |
| 12 | state_direction({2,3}, 1) |
|
| 13 | state_direction({2,4}, 1) |
|
| 14 | 函数结束 |
样例解释
- 评测器调用
run，其中N=2。
2-5. run 先声明了从入口出发的两条小路，以及通向出口的两条小路的方向。根据题意，这四条小路一定都是正方向，所以可以直接确定。
6-7. run 连续进行了两次异或询问，并且两次都得到了 1。这时分析三条边 (3,4)、(3,5)、(4,5) 的方向：
- 由于第 7 步只询问了
{(3,5)}，返回值是1，所以(3,5)一定是正方向； - 再结合第 6 步对
{(3,4),(3,5),(4,5)}的异或结果为1，可以推出剩余两条边的方向只可能落在原题图示给出的两种方案中。
其中第二种方案会形成一个有向环，但题目明确保证图中不存在有向环，所以只能选择第一种方案。
因此 run 在第 8-10 步声明：
(3,4)为正方向；(3,5)为正方向；(4,5)为正方向。
- 接着，
run询问{(2,3),(2,4)}的异或值，得到0。这说明这两条边方向相同。
于是它们也只有原题图示中的两种可能方向方案。
12-13. 如果采用第一种方案，那么与点 2 相连的所有边都会指向点 2。但题目中只有一个点允许“所有相邻边都指向它”，那就是出口；而点 2 显然不是出口。
因此只能采用第二种方案，于是：
(2,3)为正方向；(2,4)为正方向。
- 函数结束，总共使用了
3次询问。
说明
本题为交互 / 提交函数题，因此没有传统意义上的样例输入与样例输出。上面的“样例通信”展示的是选手程序与评测器之间的一次交互过程。