#6734. 「2020 集训队论文」图上的游戏

内存限制:512 MiB 时间限制:5000 ms 题目类型:交互
上传者: EntropyIncreaser

题目描述

这是一道交互题。

注意:本题只支持以下语言的提交:

  • C++
  • C++ 11
  • C++ 17
  • C++ (NOI)
  • C++ 11 (NOI)
  • C++ 11 (Clang)
  • C++ 17 (Clang)

小 Z 有一张 n 个点 m 条边的没有自环的无向图。小 U 想要知道这张图的样子,但小 Z 不肯告诉它。

小 Z:我可以告诉你这张图是连通的,点从 0 标号至 n-1 ,边从 0 标号至 m-1

小 U:好那删掉一条边后,这张图的连通状况如何呢?

小 Z:反正你也猜不出来,就这样吧。你每次告诉我一个边的编号的集合 S ,再给定一个点 u ,然后我可以帮你计算把编号在 S 中的边连接后, 0 号点与点 u 是否连通。

听到小 Z 的这句话后,小 U 苦思冥想,仍然不知道如何才能问出这张图的每条边到底连接哪两个端点。

因此他找到了你,想让你帮他问出这张图的信息。我们保证这张图是预先生成的,也就是说不会随小 U 的询问而改变。并且你不能询问太多次,你需要在 \mathbf{30000} 次内得到这张图的信息!

实现细节

你不需要实现主函数,你只需实现一个函数:

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

这个函数应该返回一个长度为 m 的数组 e ,其中 e[i] 表示第 i 条边连接的两个端点(顺序无关)。

同时,你需要在你提交的文件中包含 graph.h 头文件,我们下发了 sample_graph.cpp 供你做参考。

你所实现的函数可以调用交互库中的函数:

bool query(int u, std::vector<int> s)

这个函数中 u 是一个 [0, n-1] 中的整数, s 是一个长度为 m int 数组,且值只能为 0 1 。若 s[i] = 1 ,则表示 i 是否在小 U 询问的集合 S 中,否则不在集合 S 。这个函数的意义是给定 u S ,询问 0 号点能否通过编号在 S 中的边到达 u

测试程序方式

你可以调用编译命令:

g++ graph.cpp grader.cpp -o grader -O2 -std=c++11

对于得到的 grader,会按如下方式输入数据:

第一行输入两个正整数 n,m

接下来 m 行,每行输入两个整数 u_i, v_i ,表示图中的一条边。

如果你的答案正确,grader 会输出 Accepted!You made x attempt(s).,其中 x 是你调用的 query 函数的次数。

否则你会得到一些错误信息。你可以对照着 grader.cpp 的代码和它输出的错误信息来判断你的错误原因。grader 不会检验你的输入是否正确!

样例

grader 输入为

3 3
0 1
1 2
2 0

一种正确的输出为

Accepted!You made 30000 attempt(s).

其他输入样例见下发文件中 graph1~5.in,其中 graph5.in 满足子任务 6 的条件。

数据范围与提示

对于 100\% 的数据,保证 1\le n, m\le 600

子任务编号 分值 特殊性质
1 6 n,m\le 25, m = n-1
2 10 n,m\le 25
3 17 m=n-1 ,且图中每个点的度数 \le2 0 号点度数为 1
4 24 m=n-1
5 19 对于 0\le i<n-1 ,第 i 条边连接 i,i+1
6 13 编号 <n-1 的边构成一颗树
7 11