Public Judge

pjudge

Time Limit: 1 s Memory Limit: 256 MB Total points: 75 Communication
Statistics

2022 年 10 月 8 日 更新:请注意,本题原始的交互库中,在 Alice 向 Bob 发送长度为 $0$ 的串时,会导致 Bob 的交互库在读入信息时失败。该问题已经修正,所有的提交记录均会被重测。感谢 hos_lyric 的反馈。


这是一道通信题。

一场考试正在进行。

这次考试的内容非常简单——给定一张 $N$ 个点 $M$ 条边的无向图 $G=(V,E)$,第 $i$ 条边($0 \leq i < M$)的两端点为 $(U_i, V_i)$($0 \leq U_i, V_i < N$)。保证图中不含有重边与自环。考试的任务是给每个点赋一个 $0 \sim 7$ 中的颜色 $C_i$,满足任意一条边的两个端点的颜色不同。

Alice 通过她的神力很快得到了一组合法的染色方案通过了考试。

Bob 也想要得到这样一个方案,于是它决定偷偷与 Alice 进行交流。Alice 可以向 Bob 发送一个长为 $L$ 的 0/1 串 $X$,向 Bob 提示一些信息。随后,Bob 需要构造出任意一个合法的 8 - 染色方案。

形式化的题意

两个程序各有一张无向图。第一个程序 Alice 拥有一个合法的 8 - 染色方案,它可以向第二个程序发送信息,使得第二个程序能够构造任意一个合法的 8 - 染色方案。

实现细节

这是一道通信题,本题仅支持 C++ 语言。你需要提交两个程序。

Alice

你需要提交的第一个程序为 Alice,其描述 Alice 的策略。

你需要包含头文件 Alice.h,并实现以下函数:

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C);
  • 在每个测试点中,该函数会被调用恰好一次。
  • N 表示图 $G$ 的点数 $N$。
  • M 表示图 $G$ 的边数 $M$。
  • U, V 均为长为 $M$ 的数组,描述图中的边。
  • C 为一个长为 $N$ 的数组 $C_0, C_1, \cdots, C_{N-1}$($0 \leq C_i < 8$),描述 Alice 所构造出的 8 - 染色中,第 $i$ 个点的颜色。
  • 该函数需要返回一个数组 $X$:
    • 设 $L = |X|$。
    • 你需要保证 $0 \leq L < 6 \times 10^5$。
    • 你需要保证对任意 $0 \leq i < L$,均有 $X_i \in \{0, 1\}$
  • 在每组测试数据中,该函数会被调用恰好一次。

Bob

你需要提交的第二个程序为 Bob,其描述 Bob 的策略。

你需要包含头文件 Bob.h,并实现以下函数:

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X);
  • 在每个测试点中,该函数会被调用恰好一次。
  • N 表示图 $G$ 的点数 $N$。
  • M 表示图 $G$ 的边数 $M$。
  • U, V 均为长为 $M$ 的数组,描述图中的边。
  • X 为 Alice 所返回的数组 $X$。
  • 该函数需要返回一个数组 $C'$:
    • 你需要保证 $|C'| = N$。
    • 你需要保证对任意 $0 \leq i < N$,均有 $0 \leq C'_i < 8$。
    • 你需要保证对任意 $0 \leq i < M$,均有 $C'_{U_i} \ne C'_{V_i}$。
  • 在每组测试数据中,该函数会被调用恰好一次。

样例交互库

下发文件中含有样例交互库 grader.cpp,你可以通过以下命令编译得到可执行文件 answer

g++ grader.cpp Alice.cpp Bob.cpp -o answer -O2

可执行文件将从标准输入(stdin)中读取以下格式的输入数据:

  • 输入的第一行包含两个整数 $N, M$。
  • 接下来 $M$ 行,每行两个整数 $U_i, V_i$。
  • 接下来一行,包含 $N$ 个整数 $C_0, C_1, \cdots, C_{N-1}$。

若你的程序正常结束,则可执行文件将向标准输出中按照以下格式输出:

  • 输出一行,包含 $N$ 个整数 $C'_0, C'_1, \cdots, C'_{N-1}$。

在最终评测时,程序 AliceBob 将被分别编译并在两个不同的进程中运行。本题的时间限制(1.0 秒)与空间限制(256 MiB)均指每个进程所能使用的时间与空间的最大值。在任意一个进程中超过该限制都会导致发生相应的错误。保证在最终评测时,三个程序各自的交互库使用的时间不超过 0.1 秒,空间不超过 16 MiB,即选手至少有 0.9 秒的时间与 240 MiB 的空间可用。

样例数据

样例输入

10 14
2 8
3 2
2 4
6 5
3 5
4 8
8 6
7 6
2 7
0 6
4 7
1 4
3 0
4 3
1 5 2 0 4 5 2 1 7 2

样例输出

0 0 0 1 2 0 1 3 3 0

子任务

请注意,本题满分为 75 分。

对于所有数据,$1 \leq N \leq 2 \times 10^{5}, 0 \leq M \leq 5 \times 10^5$。

在每个测试点中,如果你超出了时间限制(1.0 秒),超出了空间限制(256 MiB),或发生了运行时错误,或最终构造的方案不合法,则你的得分为 $0$。

  • 请注意:时间限制指你的两个程序的运行时间的最大值不能超过 1.0 秒。空间限制指你的两个程序所使用的空间的最大值不能超过 256 MiB。
  • 在任何合法(可以取得分数)的交互过程中,交互库在两次调用时所使用的内存不会超过 12 MiB,时间不会超过 0.05 秒。

否则,你的得分取决于 $L = |X|$ 的值:

  • 参数 $S$ 与 $L$ 的值有关:
    • 若 $L \leq 2.5 \times 10^5$,则 $S = 75$。
    • 若 $2.5 \times 10^5 < L \leq 6 \times 10^5$,则 $S = 2 + 70 \times \left(\frac{600\,000 - L}{350\,000}\right)^2$。
    • 否则, $S = 0$。
  • 最终你的得分为 $S$。

即,为了获得满分,你最多只能传递长为 $2.5 \times 10^5$ 的二进制串。