QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Communication
[+7]

# 141. 8 染色

统计

这是一道通信题。

一场考试正在进行。

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

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

Bob 也想要得到这样一个方案,于是它决定偷偷与 Alice 进行交流。Alice 可以向 Bob 发送一个长为 L0/1X,向 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 均为长为 M1 的数组,描述图中的边。
  • C 为一个长为 N 的数组 C0,C1,,CN10Ci<8),描述 Alice 所构造出的 8 - 染色中,第 i 个点的颜色。
  • 该函数需要返回一个数组 X
    • L=|X|
    • 你需要保证 0L<6×105
    • 你需要保证对任意 0i<L,均有 Xi{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 均为长为 M1 的数组,描述图中的边。
  • X 为 Alice 所返回的数组 X
  • 该函数需要返回一个数组 C
    • 你需要保证 |C|=N
    • 你需要保证对任意 0i<N,均有 0Ci<8
    • 你需要保证对任意 0i<M,均有 CUiCVi
  • 在每组测试数据中,该函数会被调用恰好一次。

样例交互库

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

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

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

  • 输入的第一行包含两个整数 N,M
  • 接下来 M 行,每行两个整数 Ui,Vi
  • 接下来一行,包含 N 个整数 C0,C1,,CN1

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

  • 输出一行,包含 N 个整数 C0,C1,,CN1

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

样例数据

样例输入

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

子任务

对于所有数据,1N2×105,0M5×105

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

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

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

  • 参数 SL 的值有关:
    • L2.5×105,则 S=100
    • 2.5×105<L6×105,则 S=2+95×(600000L350000)2
    • 否则, S=0
  • 参数 K1t 的值有关:
    • t0.5,则 K1=1
    • 0.5<t2.0,则 K2=(112t)+0.05
    • 否则,t=0
  • 参数 K2m 的值有关:
    • m32,则 K2=1
    • 32<t256,则 K2=(11256m)
    • 否则,K2=0
  • 最终你的得分为 K1×K2×S

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

This is a communication problem.

An exam is taking place.

The content of this exam is quite simple—given an undirected graph G=(V,E) with N vertices and M edges, where the i-th edge (0i<M) connects the two vertices (Ui,Vi) (0Ui,Vi<N). It is guaranteed that the graph contains no multiple edges or self-loops. The task is to assign each vertex a color from the set {0, 1, 2, 3, 4, 5, 6, 7} such that the two endpoints of any edge have different colors.

Alice, using her magical powers, quickly finds a valid coloring solution and passes the exam.

Bob also wants to find such a solution, so he decides to secretly communicate with Alice. Alice can send Bob a binary string X of length L to give him some hints. Subsequently, Bob needs to construct any valid 8-coloring solution.

Implementation Details

This is a communication problem, and the problem only supports the C++ language. You need to submit two programs.

Alice

The first program you need to submit is Alice, which describes Alice's strategy.

You need to implement the following function:

std::vector <int> Alice(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> C);
  • N represents the number of vertices N in the graph G.
  • M represents the number of edges M in the graph G.
  • U, V are arrays of length M1 that describe the edges of the graph.
  • C is an array of length N, where C0,C1,,CN1 (0Ci<8) describes the colors assigned by Alice in the 8-coloring.
  • This function needs to return an array X:
    • Let L=|X|.
    • You need to ensure 0L<6×105.
    • You need to ensure that for any 0i<L, Xi is either 0 or 1.
  • In each test case, this function will be called exactly once.

Bob

The second program you need to submit is Bob, which describes Bob's strategy.

You need to implement the following function:

std::vector <int> Bob(int N, int M, std::vector <int> U, std::vector <int> V, std::vector <int> X);
  • N represents the number of vertices N in the graph G.
  • M represents the number of edges M in the graph G.
  • U, V are arrays of length M1 that describe the edges of the graph.
  • X is the array returned by Alice.
  • This function needs to return an array C:
    • You need to ensure that |C|=N.
    • You need to ensure that for any 0i<N, 0Ci<8.
    • You need to ensure that for any 0i<M, CUiCVi.
  • In each test case, this function will be called exactly once.

Sample Interaction Library

The provided files include a sample interaction library grader.cpp. You can compile the executable answer using the following command:

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

The executable will read the following input format from standard input (stdin):

  • The first line of input contains two integers N and M.
  • The next M lines each contain two integers Ui and Vi.
  • The next line contains N integers C0,C1,,CN1.

If your program runs correctly, the executable will output the following format:

  • One line containing N integers C0,C1,,CN1.

Please note that the interaction library used in the final evaluation will differ from this sample interaction library. Contestants should not rely on the specific implementation of this sample library.

Sample Data

Sample Input

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

Sample Output

0 0 0 1 2 0 1 3 3 0

Subtasks

For all data, 1N2×105, 0M5×105.

In each test point, if you exceed the time limit (2.0 seconds), the space limit (256 MiB), encounter a runtime error, or the final constructed solution is invalid, your score will be 0.

  • Please note: The time limit means that the maximum runtime of both of your programs combined cannot exceed 2.0 seconds. The space limit means that the maximum space used by both of your programs combined cannot exceed 256 MiB.
  • In any valid (scorable) interaction, the interaction library will use no more than 12 MiB of memory and no more than 0.05 seconds between two calls. Therefore, you actually have at least 1.95 seconds and at least 244 MiB of space available.

Otherwise, your score depends on the value of L=|X|, the time t (in seconds) used by your program, and the memory m (in MB) used by your program:

  • The parameter S depends on the value of L:
    • If L2.5×105, then S=100.
    • If 2.5×105<L6×105, then S=2+95×(600000L350000)2.
    • Otherwise, S=0.
  • The parameter K1 depends on the value of t:
    • If t0.5, then K1=1.
    • If 0.5<t2.0, then K1=(112t)+0.05.
    • Otherwise, K1=0.
  • The parameter K2 depends on the value of m:
    • If m32, then K2=1.
    • If 32<m256, then K2=(11256m).
    • Otherwise, K2=0.
  • Finally, your score is K1×K2×S.

In summary, to achieve a perfect score, the binary string you transmit should be no longer than 2.5×105 bits, and the time used by your programs (including the interaction library) should not exceed 0.5 seconds, with memory usage not exceeding 32 MiB (including the interaction library, which means your programs should use no more than 20 MiB of space).