P11054 [IOI 2024] Sphinx's Riddle

When submitting, please do not include `sphinx.h`, and add the following at the beginning of your code: ```cpp #include int perform_experiment(std::vector E); ``` Do not submit using C++14 (GCC 9).

The Sphinx has prepared a riddle for you. You are given a graph with $N$ vertices, numbered from $0$ to $N-1$. The graph has $M$ edges, numbered from $0$ to $M-1$. Each edge connects two different vertices, and edges are bidirectional. More precisely, for each $j$ from $0$ to $M-1$, edge $j$ connects vertices $X[j]$ and $Y[j]$. There is at most one edge between any two vertices. If two vertices are connected by an edge, they are **adjacent**. For a vertex sequence $v_0, v_1, \ldots, v_k$ (for $k \ge 0$), if every pair of consecutive vertices $v_l$ and $v_{l+1}$ (for all $l$ such that $0 \le l \lt k$) are adjacent, then it is called a **path**. The path $v_0, v_1, \ldots, v_k$ **connects** vertices $v_0$ and $v_k$. In the given graph, every pair of vertices is connected by some path. There are $N + 1$ colors, numbered from $0$ to $N$. Color $N$ is special and is called the **Sphinx color**. Initially, each vertex has a color: the color of vertex $i$ ($0 \le i \lt N$) is $C[i]$. Multiple vertices may have the same color, some colors may not appear on any vertex, and no vertex initially has the Sphinx color. That is, $0 \le C[i] \lt N$ ($0 \le i \lt N$). If all vertices on a path $v_0, v_1, \ldots, v_k$ (for $k \ge 0$) have the same color, then the path is **monochromatic**. That is, it satisfies $C[v_l] = C[v_{l+1}]$ (for all $l$ such that $0 \le l \lt k$). Moreover, two vertices $p$ and $q$ ($0 \le p \lt N$, $0 \le q \lt N$) are in the same **monochromatic component** if and only if they are connected by some monochromatic path. You know the graph structure (the vertices and edges), but you do not know the colors of the vertices. You want to find out the vertex colors by performing **recoloring experiments**. In one recoloring experiment, you may recolor any number of vertices. More precisely, in an experiment you provide an array $E$ of length $N$, and for each $i$ ($0 \le i \lt N$), $E[i]$ is between $-1$ and $N$ (**inclusive** of $-1$ and $N$). After recoloring, the color of each vertex $i$ becomes $S[i]$, where: * If $E[i] = -1$, then $S[i] = C[i]$, i.e. the original color of vertex $i$ before recoloring. * Otherwise, $S[i] = E[i]$. Note that you may use the Sphinx color during recoloring. After setting the color of each vertex $i$ to $S[i]$ ($0 \le i \lt N$), the Sphinx announces the number of monochromatic components in the graph. This new coloring is only valid for this experiment, so **after the experiment ends, all vertex colors return to the initial ones**. Your task is to determine the colors of all vertices using at most $2\,750$ recoloring experiments. If you correctly determine, for every pair of adjacent vertices, whether they have the same color, you will also receive partial score. ### Implementation details You need to implement the following function: ``` std::vector find_colours(int N, std::vector X, std::vector Y) ``` * $N$: the number of vertices in the graph. * $X$, $Y$: two arrays of length $M$ describing the edges of the graph. * The function should return an array $G$ of length $N$, representing the colors of the vertices. * For each test case, this function is called exactly once. This function can perform recoloring experiments by calling: ``` int perform_experiment(std::vector E) ``` * $E$: an array of length $N$ specifying how to recolor the vertices. * This function returns the number of monochromatic components after recoloring as specified by $E$. * This function may be called at most $2\,750$ times. The grader is **not adaptive**. That is, the vertex colors are fixed before `find_colours` is called.

The sample grader reads input in the following format: ``` N M C[0] C[1] ... C[N-1] X[0] Y[0] X[1] Y[1] ... X[M-1] Y[M-1] ```

The sample grader prints your answer in the following format: ``` L Q G[0] G[1] ... G[L-1] ``` Here, $L$ is the length of the array $G$ returned by `find_colours`, and $Q$ is the number of calls to `perform_experiment`.

Consider the following function call: ``` find_colours(4, [0, 1, 0, 0], [1, 2, 2, 3]) ``` In this example, suppose the (hidden) vertex colors are $C = [2, 0, 0, 0]$, as shown in the figure below. The vertex colors are also shown as numbers in the labels at the upper-right corner of the vertices.  Suppose the function calls `perform_experiment` as follows: ``` perform_experiment([-1, -1, -1, -1]) ``` This call does not recolor any vertex, so all vertices keep their original colors. Vertices $1$ and $2$ both have color $0$. Therefore, the path $1, 2$ is a monochromatic path, so vertices $1$ and $2$ are in the same monochromatic component. Vertices $1$ and $3$ both have color $0$. However, since there is no monochromatic path connecting them, they are in different monochromatic components. In total, there are $3$ monochromatic components: vertex sets $\{0\}$, $\{1, 2\}$, and $\{3\}$. Therefore, this call returns $3$. Now suppose the function calls `perform_experiment` as follows: ``` perform_experiment([0, -1, -1, -1]) ``` This call recolors only vertex $0$ to color $0$, producing the result shown below.  Now all vertices belong to a single monochromatic component, so this call returns $1$. From this, we can infer that vertices $1$, $2$, and $3$ all have color $0$. Suppose the function also calls `perform_experiment` as follows: ``` perform_experiment([-1, -1, -1, 2]) ``` This call recolors vertex $3$ to color $2$, producing the result shown below.  Now there are $2$ monochromatic components: vertex sets $\{0, 3\}$ and $\{1, 2\}$. Therefore, this call returns $2$. From this, we can infer that vertex $0$ has color $2$. Then `find_colours` returns the array $[2, 0, 0, 0]$. Since $C = [2, 0, 0, 0]$, you get full score. There are also many other possible return values, such as $[1, 2, 2, 2]$ or $[1, 2, 2, 3]$, which can earn $50\%$ of the score. ### Constraints * $2 \le N \le 250$ * $N - 1 \le M \le \frac{N \cdot (N - 1)}{2}$ * For all $j$ such that $0 \le j \lt M$, $0 \le X[j] \lt Y[j] \lt N$. * For all $j$ and $k$ such that $0 \le j \lt k \lt M$, $X[j] \neq X[k]$ or $Y[j] \neq Y[k]$. * Every pair of vertices is connected by some path. * For all $i$ such that $0 \le i \lt N$, $0 \le C[i] \lt N$. | Subtask | Score | Additional constraints | | :-----: | :----: | ---------------------- | | 1 | $3$ | $N = 2$ | | 2 | $7$ | $N \le 50$ | | 3 | $33$ | The given graph is a path: $M = N - 1$, and vertices $j$ and $j+1$ are adjacent ($0 \leq j < M$). | | 4 | $21$ | The given graph is complete: $M = \frac{N \cdot (N - 1)}{2}$, and any two vertices are adjacent. | | 5 | $36$ | No additional constraints. | In each subtask, if your program correctly determines, for every pair of adjacent vertices, whether they have the same color, you will also receive partial score. More precisely, if for all test cases `find_colours` returns an array $G$ that is exactly the same as $C$ (i.e. for all $i$ such that $0 \le i \lt N$, $G[i] = C[i]$), you will receive the full score for that subtask. Otherwise, if for all test cases in a subtask the following conditions hold, you will receive $50\%$ of the score for that subtask: * For all $i$ such that $0 \le i \lt N$, $0 \le G[i] \lt N$. * For all $j$ such that $0 \le j \lt M$, we have: * $G[X[j]] = G[Y[j]]$ if and only if $C[X[j]] = C[Y[j]]$. Translated by ChatGPT 5