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 (0≤i<M) connects the two vertices (Ui,Vi) (0≤Ui,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 M−1 that describe the edges of the graph.
C
is an array of length N, where C0,C1,⋯,CN−1 (0≤Ci<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 0≤L<6×105.
- You need to ensure that for any 0≤i<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 M−1 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 0≤i<N, 0≤C′i<8.
- You need to ensure that for any 0≤i<M, C′Ui≠C′Vi.
- 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,⋯,CN−1.
If your program runs correctly, the executable will output the following format:
- One line containing N integers C′0,C′1,⋯,C′N−1.
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, 1≤N≤2×105, 0≤M≤5×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 L≤2.5×105, then S=100.
- If 2.5×105<L≤6×105, then S=2+95×(600000−L350000)2.
- Otherwise, S=0.
- The parameter K1 depends on the value of t:
- If t≤0.5, then K1=1.
- If 0.5<t≤2.0, then K1=(1−12t)+0.05.
- Otherwise, K1=0.
- The parameter K2 depends on the value of m:
- If m≤32, then K2=1.
- If 32<m≤256, then K2=(1−1256m).
- 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).