Editorial for DMOPC '17 Contest 1 P6 - Land of the Carrot Trees
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, a brute-force DFS suffices.
Time complexity:
To obtain full points, split the operations into blocks. For each block, precompute all connected components which exist before the block (also remove any edges mentioned in the
R
queries of the block before computing). Note that there are at most nodes involved in the operations in the block. For each connected component containing such a node, assign this component a root and compute the
distance from each node in the component to the root. For each
A
operation in the block, make sure to update both the real edges as well as the edges between the connected components. Similarly, for each R
operation, update both types of edges. Finally, for each Q
operation, DFS within the connected components to obtain the answer. The final time complexity is . When
is
, this becomes
.
Time Complexity:
Comments