QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Communication

# 141. 8 染色

Statistics

这是一道通信题。

一场考试正在进行。

这次考试的内容非常简单——给定一张 $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 - 染色方案。

实现细节

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

Alice

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

你需要实现以下函数:

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-1$ 的数组,描述图中的边。
  • 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 的策略。

你需要实现以下函数:

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-1$ 的数组,描述图中的边。
  • 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}$。

请注意,在最终评测时,使用的交互库与该样例交互库有所不同。选手不应依赖该交互库的实现。

样例数据

样例输入

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

子任务

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

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

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

否则,你的得分取决于 $L = |X|$ 的值、你的程序所用的时间 $t$ (单位:秒)与你的程序所用的空间 $m$ (单位:MB):

  • 参数 $S$ 与 $L$ 的值有关:
    • 若 $L \leq 2.5 \times 10^5$,则 $S = 100$。
    • 若 $2.5 \times 10^5 < L \leq 6 \times 10^5$,则 $S = 2 + 95 \times \left(\frac{600\,000 - L}{350\,000}\right)^2$。
    • 否则, $S = 0$。
  • 参数 $K_1$ 与 $t$ 的值有关:
    • 若 $t \leq 0.5$,则 $K_1=1$。
    • 若 $0.5 < t \leq 2.0$,则 $K_2 = (1-\frac{1}{2}t) + 0.05$。
    • 否则,$t = 0$。
  • 参数 $K_2$ 与 $m$ 的值有关:
    • 若 $m \leq 32$,则 $K_2=1$。
    • 若 $32 < t \leq 256$,则 $K_2 = (1-\frac{1}{256}m)$。
    • 否则,$K_2 = 0$。
  • 最终你的得分为 $K_1 \times K_2 \times S$。

即,为了获得满分,你最多只能传递长为 $2.5 \times 10^5$ 的二进制串,使用的时间不能超过 $0.5$ 秒(含交互库所用时间),空间不能超过 $32$ MiB(含交互库所用空间,即你应当使用不超过 $20$ MiB 空间)。