UOJ Logo Universal Online Judge

UOJ

#751. 【UNR #6】神隐

附件下载 统计

这是一道交互题。

hehe 蚤决定花费几天时间,游览下山市的最著名的旅游景点 —— 吓山。

吓山,以高低纵横,崔巍秀丽,错综复杂的地形闻名。据说无论用什么地图导航,都不能保障你在山中不迷路。

之所以会出现这样的情况,是因为吓山中的路,在没有光的时候都会发生 “神隐”。在“神隐”状态下,人们无法察觉到这条路的存在,很容易就迷路了。

吓山的地图可以简化为一个 $n$ 个节点,编号为 $0 \sim n-1$ 的树。它有 $n - 1$ 条边,其中第 $i$ 条边为 $(u_i, v_i)$($0 \leq i \lt n - 1$)。每条路上都装有路灯。

为了攻略吓山,hehe 蚤和它的小伙伴们试图绘制吓山的地图。

  1. hehe 蚤事先从吓山管理员那里拿到了吓山每条路的路灯的控制权。hehe 蚤会进行若干次询问,每次询问时 hehe 蚤都会打开一部分路的路灯,并关闭剩下的路灯。当一条路上的路灯打开时,这条路就真实存在;当路灯关闭时,这条路就会 “神隐”,等效于不存在。
  2. 对于每个询问,hehe 蚤的小伙伴们都会进行一番实地考察,告诉 hehe 蚤吓山在当前状态下的哪些节点是可以通过道路相互连通的。
  3. 最后 hehe 蚤会根据询问结果总结出一份地图,即恢复出这棵树的形态。

为了更高效地解决问题,hehe 蚤将其抽象为了一道交互题。有一棵未知的树,你需要对交互库进行若干次询问,来恢复这棵树的形态。每次询问时,你需要给出一个长度为 $n - 1$ 的 $01$ 向量 $A$,然后交互库会将每条满足 $A_i = 1$ 的边 $(u_i, v_i)$ 加入一张新的空图 $G$ 中,并返回其中每一个连通块(再删除这个图)。最后,你需要输出这棵树的所有边(顺序、方向任意)。

任务

本题仅支持符合 C++ 11 标准及以上的 C++ 语言。

你必须引用 tree.h

你需要实现下面的过程:

std::vector<std::pair<int, int>> solve(int n);

这个过程会被恰好调用一次。

其中 $n$ 为树的节点数量,你需要返回这棵树的所有边,边的顺序、方向任意。

你可以调用以下函数:

std::vector<std::vector<int>> query(std::vector<int> vec);

你需要保证 $vec$ 是个 $01$ 向量,且长度为 $n-1$。

它会返回在一张空图加入指定边后的所有连通块,每个连通块以 std::vector<int> 存储,再将所有连通块用 std::vector 存储返回。

这个函数至多被调用 $\mathrm{limit}$ 次。

评测方式

样例评测库将读入如下格式的输入数据:

第一行两个整数 $n, \mathrm{limit}$。

接下来 $n - 1$ 行,每行两个整数 $u_i, v_i$ 表示树的一条边。

样例评测库将输出如下格式的输出数据:

如果你的返回结果错误或交互过程不合法,则评测库会输出 Wrong Answer 并输出错误原因。

否则输出两行,第一行为 Accepted!,第二行输出你使用 query 的次数。

交互式类型的题目怎么本地测试

最终测试中,树是确定的,不会因为你的询问而改变,并且最终评测库与下发评测库仅有反作弊上的差别。

样例一

input

5 22
0 3
0 2
1 0
4 2

output

Accepted!
0 calls

样例二

见附件下载中的 ex_tree2.inex_tree2.ans,该样例服从子任务二的限制。

样例三

见附件下载中的 ex_tree3.inex_tree3.ans,该样例服从子任务四的限制。

数据范围与提示

子任务编号 $n\leq$ $\mathrm{limit}=$ 分值
$1$ $7$ $22$ $10$
$2$ $2000$ $22$ $20$
$3$ $2000$ $14$ $20$
$4$ $131072$ $34$ $20$
$5$ $131072$ $20$ $30$

对于所有数据(包含 hack 数据):

$1 \leq n \leq 131072, \mathrm{limit} \leq 34$。

如果 $n \leq 2000$,则 $\mathrm{limit} \geq 14$。

否则 $\mathrm{limit} \geq 20$。

保证合法的交互过程中,交互库不会使用超过 $\texttt{0.5s}$ 的时间和 $\texttt{32MB}$ 的空间。

时间限制:$\texttt{3s}$

空间限制:$\texttt{512MB}$