UOJ Logo Universal Online Judge

UOJ

#592. 新年的聚会

附件下载 统计

这是一道交互题。

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

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

为了救出神犇,你需要打探出黑衣人 03 手下之间的关系,黑衣人 03n 个手下,编号为 0n1,其中有 m 对手下 ai, bi 之间关系不佳。

你决定举办好多次聚会,每次聚会可以邀请一些黑衣人 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 分。

评测方式

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

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

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

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

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

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

样例一

input

2 1
0 1

output

1 2

explanation

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

样例二

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

限制与约定

对于所有数据,1n1000,1m2000

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

编号 聚会个数上限 聚会总人数上限 分值
1 499500 107 25
2 50000 107 35
3 50000 106 40

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

若聚会个数不超过 500000,且聚会总人数不超过 107,交互库运行时间不会超过 2s

若聚会个数不超过 50000,交互库运行时间不会超过 200ms

保证交互库使用空间不超过 4MB

时间限制3s

空间限制512MB

下载

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