Contest Duration: - (local time) (100 minutes) Back to Home

## G - Propagation Editorial by en_translator

If you naively simulate the operations of queries, we need at worst an $$\mathrm{\Theta}(QN)$$ time to process all the queries, so it is hopeless to finish it in the time limit.
Instead, for acceleration, let us define a constant $$B$$, and divide $$N$$ vertices into “a group of vertices with degrees more than or equal to $$B$$” and “a group of vertices with degrees less than $$B$$,” and treat them differently depending on the group.

We inspect the queries in the order of input. For $$i = 1, 2, \ldots, Q$$, we process Query $$i$$ through the following steps, Step 1 through Step 3.

Step 1: Replace the integer currently written on Vertex $$x_i$$ to the correct value (described later).
Step 2: Let $$X$$ be the “correct” value written on Vertex $$X$$. Step 3: Depending on whether the degree of Vertex $$x_i$$ is less than $$B$$ or not, perform either (a) or (b) described below.

#### (a) If the degree of Vertex $$x_i$$ is less than $$B$$

For every vertex adjacent to Vertex $$x_i$$, we replace the integer written on it with $$X$$. Here, we also record to each vertex that “the number has been replaced by Query $$i$$.”
The time required for this process is $$O(B)$$, since Vertex $$x_i$$ has a degree less than $$B$$.

#### (a) If the degree of Vertex $$x_i$$ is more than or equal to $$B$$

Instead of replacing all the integers written on the vertices adjacent to Vertex $$x_i$$, we place a signboard to Vertex $$x_i$$ indicating that “all the integers written on the vertices adjacent to this vertex has been replaced to $$X$$ by Query $$i$$.” If there was already a signboard placed by a query in the past on Vertex $$x_i$$, we remove the signboard and retain only the latest one.
Placing and removing a signboard can be achieved in an $$O(1)$$ time, implemented as updates of variables.

#### Regarding with Step 1: “Replace the integer currently written on Vertex $$x_i$$ to the correct value”

In the case (b) above, we do not update the vertex that has to be updated, but just place a signboard instead. Therefore, right before performing Step 1, the integer currently written on Vertex $$x_i$$ may be different to the integer that actually should be written on. So, we have to check all the signboards placed at vertices adjacent to Vertex $$x_i$$ with degrees more than or equal to $$B$$ in order to reflect the update applied to the integer written on Vertex $$x_i$$.
Since there are at most $$2M/B$$ vertices with degrees more than or equal to $$B$$, this step costs $$\mathrm{O}(M/B)$$ time.

This way, we can process all the queries in a total of $$\mathrm{O}(Q(B+M/B))$$ time. We can set the value $$B$$ to about $$\sqrt{M}$$, so that every query is processed in an $$\mathrm{O}(Q\sqrt{M})$$ time, so that the entire problem is solved in a total of $$\mathrm{O}(Q\sqrt{M})$$ time.

posted:
last update: