UOJ Logo Universal Online Judge

UOJ

#592. 新年的聚会

附件下载 统计

这是一道交互题。

由于某些原因本题仅支持 C++, C++11 语言的提交。

你通过你派遣到黑衣人中的卧底,知晓了神犇被黑衣人 $03$ 当做了坐骑,并取名为 ak's cow,并且它过几天就要被吃了。

为了救出神犇,你需要打探出黑衣人 $03$ 手下之间的关系,黑衣人 $03$ 有 $n$ 个手下,编号为 $0\sim n-1$,其中有 $m$ 对手下 $a_i$, $b_i$ 之间关系不佳。

你决定举办好多次聚会,每次聚会可以邀请一些黑衣人 $03$ 的手下,但是邀请的名单必须给每个人看,如果有人发现名单里存在和自己关系不佳的人,他就会拒绝来聚会,这次聚会就不能举办成功。

由于时间紧急,你最多举办聚会次数不能太多,由于资金有限,所有聚会的人数和不能太大,而你需要知道哪些手下之间关系不佳。

任务

你必须引用 meeting.h 头文件。

你需要实现下面的过程:

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

其中 $n$ 是黑衣人 $03$ 的手下数量,而关系不佳的手下对数你并不知道,你需要返回关系不佳的手下,顺序任意。

你可以调用以下过程和交互库进行交互:

bool meeting(std::vector<int> set);

该函数表示你就将举办一场聚会,其中 set 是一个包含要邀请的人的编号的 vector。当聚会能正常举办时返回值为 true,否则为 false。你必须保证所有编号在合法范围内且互不相同,不然你会获得 $0$ 分。

评测方式

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

第一行包括两个正整数 $n$ 和 $m$,表示黑衣人 $03$ 的手下个数,与关系不佳的手下对数。

接下来 $m$ 行,每行两个整数 $x_i, y_i$,表示手下 $x_i$ 与 $y_i$ 关系不佳,一对关系不佳的手下只会被读入一次,且没有手下和自己关系不佳。

在最终测试中,关系不佳的手下是确定的,不会因为你的询问而改变。

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

如果程序正常运行,则输出两个整数 $cnt, size$,表示举办聚会个数与总人数,否则会输出错误信息。

样例一

input

2 1
0 1

output

1 2

explanation

我们可以直接调用 meeting([0, 1]) 来检验唯一一对可能关系不佳的手下,我们发现它们关系不佳于是可以返回 [(0, 1)]

样例二

见下载文件中的 ex_meeting2.inex_meeting2.out

限制与约定

对于所有数据,$1 \leq n \leq 1000, 1 \leq m \leq 2000$。

对于所有测试点,我们会根据以下方式计分:

编号 聚会个数上限 聚会总人数上限 分值
$1$ $499500$ $10^7$ $25$
$2$ $50000$ $10^7$ $35$
$3$ $50000$ $10^6$ $40$

对每个部分,你满足其要求就可以获得其分数。

若聚会个数不超过 $500000$,且聚会总人数不超过 $10^7$,交互库运行时间不会超过 $2\texttt{s}$。

若聚会个数不超过 $50000$,交互库运行时间不会超过 $200\texttt{ms}$。

保证交互库使用空间不超过 $4 \texttt{MB}$。

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

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

下载

样例数据与样例评测库下载