【UNR #4】网络恢复 - 题目 - Universal Online Judge

这是一道交互题。

出题人 02 喜欢网上冲浪。可是这天，他所在的小区的网络坏掉了，于是他喊来了你帮忙修一修。

小区的网络由 $N$ 个网络结点和 $M$ 条信道组成，可以被看作是一张 $N$ 个点 $M$ 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边，且没有自环）。点从 $1 \sim N$ 编号，边从 $1 \sim M$ 编号。目前，你只知道信道的总数是 $M$ ，并且还掌握着每条信道的管理权限，然而你并不知道每条信道连接着哪两个结点。

为了恢复出网络结构，你可以使用一种土办法：重启大法！

当然重启也是需要智慧的。具体来说，你可以进行若干次操作，每次操作方式如下：

给每个结点 $i$ 标上一个自己定的权值 $a_{i}$ ；
选取一个信道的子集 $S$ ，把不在 $S$ 里的信道都关闭，只让 $S$ 里的信道保持开启状态；
此时，每个结点 $i$ 会自动计算出与 $i$ 通过开启状态的信道直接相邻的所有点 $v$ 的 $a_{v}$ 异或和，记为 $b_{i}$ ；
你通过管理员权限获取所有结点的 $b_{i}$ 值，然后关闭的信道都重启，网络恢复至原状。

请你在不超过 $50$ 次操作内，求出所有信道构成的集合。

注意，你只需要求出信道的集合。即，你只需要恢复出哪些结点之间有信道，不用恢复出每条信道对应的编号。

实现细节

你不需要，也不应该实现主函数，你只需要实现函数 $Solve(N, M)$ ，这里的 $N$ 和 $M$ 分别表示结点和信道的个数。你可以通过调用如下函数来和交互库进行交互：

$Query(A,S)$
- 这个函数可以暂时删去编号不在 $S$ 中的信道，并将 $i$ 号点的 $a_{i}$ 设置成 $A [i - 1]$ ；
- 交互库会返回一个大小为 $N$ 的 vector $B$ ， $B [i - 1]$ 表示 $i$ 号点的 $b_{i}$ ；
- 你需要保证对 $S$ 中的任意元素 $x$ ，有 $1 \leq x \leq M$ 且互不相同，同时你需要保证 $A$ 的大小恰好为 $N$ ；
- $A, S, B$ 均为 vector；
- $A, B$ 中元素类型为 unsigned long long， $S$ 中元素类型为 int。
$Report(x, y)$
- 这个函数可以向交互库汇报一条你发现的连接 $x$ 和 $y$ 的信道；
- 你需要保证 $1 \leq x, y \leq N$ ；
- $x, y$ 均为 int；
- 你必须恰好将所有信道报告一次，否则你的程序将会判定为错误。

评测时，交互库会恰好调用 $Solve$ 一次。

本题保证所使用的图在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。

生成数据时，图是按一定方式从 $N$ 个点， $M$ 条边的简单无向图中随机选取的（见限制与约定一节）。

数据保证在调用次数限制下，交互库运行所需的时间不超过 2.5s；交互库使用的内存大小固定，且不超过 128MB。

实现方法

本题仅支持 C++ 语言。附加文件中已经提供了一个 template_explore.cpp，请将这个文件拷贝一份，重命名为 explore.cpp，然后在其基础上答题。

请确保你的程序开头有 #include "explore.h"。
你需要实现的函数 $Solve$ 的接口信息如下：
- void Solve(int N, int M);
你可以调用的交互函数的接口如下：
- vector<unsigned long long> Query(vector<unsigned long long> A, vector<int> S);
- void Report(int x,int y);

测试程序方式

试题目录下的 grader.cpp 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

编译方法：
- 你需要在本题目录下使用如下命令编译得到可执行程序：
  - g++ grader.cpp explore.cpp -o explore -O2 -lm
对于编译得到的可执行程序：
- 可执行文件将从标准输入读入以下格式的数据：
  - 第一行包含两个整数 $N, M$ ，意义如题面描述。
  - 接下来 $M$ 行，每行两个整数 $x, y$ ，描述一条连接 $x$ 号点与 $y$ 号点的无向边。
- 读入完成之后，交互库将调用恰好一次函数 $Solve$ ，用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出 Correct ，否则会输出相应的错误信息。

假设可执行文件读入的数据为：

3 2
1 2
2 3

数据第一行的两个整数分别表示点数和边条数，即 $N = 3, M = 2$ 。

$Query(S, A)$ 调用次数不能超过 50 次。

下面是一个正确的交互过程：

选手程序	交互库	说明
	调用 $Solve(3, 2)$	开始测试
调用 $Query ({1, 2, 4}, {1})$	返回 ${2, 1, 0}$	$1$ 号节点权值为 $a [2] = 2$ , $2$ 号节点权值为 $a [1] = 1$ , $3$ 号节点权值为 $0$
调用 $Query ({1, 2, 4}, {1, 2})$	返回 ${2, 5, 2}$	$1$ 号节点权值为 $a [2] = 2$ , $2$ 号节点权值为 $a [1] xor a [3] = 5$ , $3$ 号节点权值为 $a [2] = 2$
调用 $report (1, 2)$		发现了信道 $(1, 2)$ 并记录
调用 $report (3, 2)$		发现了信道 $(3, 2)$ 并记录
运行结束并返回	向屏幕打印 Correct	交互结束，结果正确

样例一

见附加文件下载

样例二

见附加文件下载

评分方式

最终评测只会收取 explore.cpp，修改选手目录下其他文件对评测无效。

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，你得到满分，当且仅当：

你的每次函数调用均合法，且调用 $Query, Report$ 的次数分别不超过 $50$ ， $M$ 次。
由于 $Report$ 的调用次数限制为 $M$ ，你的每次调用都必须记录一条新的且存在的边；即每次调用 $report(x, y)$ 时，应满足：有一条连接 $x$ 号点和 $y$ 号点的路径，且在这次调用之前从未调用过 $report(x, y)$ 或 $report(y, x)$ 。
你实现的函数 $Solve$ 正常返回。
在 $Solve$ 函数返回时，你已经通过调用 $Report$ 记录了全部 $M$ 条信道。

限制与约定

测试点编号	$N$	$M$	特殊性质
$1$	$N = 20$	$M = 50$	无
$2$	$N = 60$	$M = 300$
$3$	$N = 3000$	$M = 10000$
$4$	$N = 6000$	$M = 30000$
$5$	$N = 49998$	$M = 49997$	图为连通图
$6$	$N = 49999$	$M = 49999$	图为连通图
$7$	$N = 50000$	$M = 50000$	无
$8$	$N = 50000$	$M = 300000$
$9$	$N = 15000$
$10$	$N = 10000$

对于 5, 6 号测试点，保证按照如下方式随机生成:

均匀随机一条不在图中的非自环的边 $(u, v)$ 。
如果加入 $(u, v)$ 后，无论之后再怎么加边，都无法使得最终的图是个连通图，那么就不加入这条边；否则加入这条边。
重复操作直至加入恰好 $M$ 条边为止。

对于其他测试数据，保证按照如下方式随机生成：

均匀随机一条不在图中的非自环的边 $(u, v)$ 。
重复操作直至加入恰好 $M$ 条边为止。

时间限制： $4 s$

空间限制： $512 MB$

提示

你的程序可以通过判断传入的 $N$ 的个位来区分上述不同的数据类型。

下载

附加文件下载

Universal Online Judge

UOJ

UOJ NOI Round #4 Day1

B. 网络恢复

实现细节

实现方法

测试程序方式

样例一

样例二

评分方式

限制与约定

提示

下载