UOJ Logo

NOI.AC

2S 666MB

#20. A

统计

本题是交互题,仅支持C++语言。

Lyra 和 Evan 喜欢周游世界,有时他们会向对方炫耀自己去过哪些国家,和在这些国家的见闻。一般来说这是令人愉悦的交谈,但为了凸显自己经历的丰富,Lyra 和 Evan 在描述时会带上夸张的成分,这就导致了,如果他们恰巧去过同一个国家,会因为维护自己吹得牛哔而吵起来……

Lyra 喜欢百花齐放,不收沾染的地域文化,而 Evan 着眼于文化之间密切的交流,所以 Lyra 访问的国家,没有任何一对国家间有航线链接,而 Evan 访问的国家,任意一对国家都有航线直接可达。 更为令人费解的是, 无论是 Lyra 还是 Evan,关于自己去过哪些国家,在其他人面前都守口如瓶。在热衷于八卦的你百般打听之下,他们决定用告诉他们去过的国家的编号——当然这编号是他们自己造的,而你跟不知道编号是怎么对应的。

然而,热衷于八卦的你才对 Lyra 和 Evan 去过哪些国家不感兴趣,你只关心他们会不会吵起来,你连忙比较 Lyra 和 Evan 告诉你去过的国家的编号集合,却发现,Lyra 和 Evan 使用的根本就是两套编号系统。

Lyra 和 Evan 决定告诉你不超过 $K$ 对编号之间的对应关系,而你想从这消息中判断他们是否会吵架。

出于好心,Evan 和 Lyra会各给你一份航线图,当然国家是用他们自己的方式编号的,编号都从 $1 \sim n$,但两人的编号方式并不相同。

交互说明

你需要在文件中包含 $\texttt{effulgence.h}$,即在文件头部写上:$\texttt{#include "effulgence.h"}$

你需要编写一个函数:

$\texttt{bool QuarrelOrNot(int n, std::vector lyra_set, std::vector evan_set);}$

其中 $n$ 表示国家的数目,$\texttt{lyra\_set}$ 和 $\texttt{evan\_set}$ 分别表示两人访问过得国家的集合(自己的编号系统中,没有重复),你可以调用一些函数来获取两张航线图,再询问一些顶点之间的对对应关系。

你的函数可以使用以下函数:

$\texttt{std::pair GetNextFlightFromLyra();}$ 会返回一个 $\texttt{std::pair}$ 表示一条 Lyra 地图上的双向航线,当返回 $(0, 0)$ 时,说明 Lyra 地图上的航线已添加完毕。

$\texttt{std::pair GetNextFlightFromEvan();}$ 会返回一个 $\texttt{std::pair}$ 表示一条 Evan 地图上的双向航线,当返回 $(0, 0)$ 时,说明 Evan 地图上的航线已添加完毕。

$\texttt{int FromLyraToEvan(int id);}$ 会返回一个整数表示在 Lyra 的地图上编号为 $\texttt{id}$ 的国家在 Evan 的地图上的编号。

$\texttt{int FromEvanToLyra(int id);}$ 会返回一个整数表示在 Evan 的地图上编号为 $\texttt{id}$ 的国家在 Lyra 的地图上的编号。

注意你的程序只有接收完毕 Lyra 和 Evan 地图上的所有航线才可以调用询问对应关系的两个函数,否则会被判错误。

你的程序可以在任意时刻返回一个答案, $\texttt{true}$ 表示两个人访问过同一个国家,而 $\texttt{false}$ 表示两个人访问的国家集合不相交。

数据不会有重边和子环。在一张地图上的航线已添加完毕之后继续调用返回航线的函数会继续返回 $(0, 0)$。

交互库输入格式

第一行四个正整数 $n, m, nL, nE$,表示国家数,双向航线数,Lyra 访问过得国家数,Evan 访问过的国家数。

第二行 $n$ 个整数为一个排列 $p_i$ 表示 Lyra 地图上编号 $i$ 的国家在 Evan 的地图上编号为 $p_i$。

第三行 $nL$ 个整数表示 Lyra 访问过的国家编号。

第四行 $nE$ 个整数表示 Evan 访问过得国家编号,注意这里的编号是在原图上(即 Lyra 的编号系统)。

接下来 $m$ 行,每行两个整数表示一条双向航线的两个端点。

交互库输出格式

若非正常结束交互库会输出错误信息。

当调用询问对应关系的函数超过 $10^6$ 次后交互库会返回错误。

否则第一行会输出一个字符串 $\texttt{Correct!}$ 表示正确 $\texttt{Wrong!}$ 表示错误。

第二行输出一个数 $K$ 表示你使用的询问次数,接下来 $K$ 行每行描述你调用的询问对应关系的函数记录。

样例输入输出

样例输入1

4 5 2 3
1 2 3 4
1 3
2 3 4
1 2
2 3
3 4
4 1
2 4

样例输出1

Correct!
3
FromLyraToEvan(1) = 1
FromLyraToEvan(2) = 2
FromLyraToEvan(3) = 3

样例输入2

见 $\texttt{/effulgence/ex_effulgence2.in}$

样例输出2

见 $\texttt{/effulgence/ex_effulgence2.ans}$

数据范围与约定

对于全部数据 $1 \leq n \leq 1000; 1 \leq nL, nE \leq 1000; 0 \leq m \leq \frac{n(n-1)}{2}$.

详细测试点和部分分信息如下表所示:

子任务 $n$ 分值 $30%$ 要求 $60%$ 要求 $100\%$ 要求
1 $ \leq 15$ $20$ $K \leq 20$ $K \leq 10$ $K \leq 5$
2 $ \leq 100$ $30$ $K \leq 50$ $K \leq 15$ $K \leq 8$
3 $ \leq 1000$ $50$ $K \leq 40$ $K \leq 15$ $K \leq 10$

提示: 数据中可能存在高度对称的图(即可能有指数级数目的不同映射),所以尽可能不要使用任何图同构近似算法。

如何测试你的程序

下发文件中有 $\texttt{grader.cpp}$ 和 $\texttt{effulgence.h}$,将你的源程序和这两个文件放在同一文件夹下并运行:

$\texttt{g++ -o effulgence grader.cpp effulgence.cpp -O2 --std=c++11}$

即可编译你的代码。

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

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

下载

样例数据下载