Editorial for COCI '15 Contest 4 #5 Galaksija

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let us choose an arbitrary node r to be the root of some tree. Let us denote with p_x the total XOR of all the curiosities on the path from node r to node x. It can be easily seen that a pair of planets x, y is boring if and only if it holds p_x \mathbin{XOR} p_y = 0 \iff p_x = p_y.

Let us notice that we can "reverse" the input data so, instead of destroying the paths, we can add them.

For connecting the components we will use the union-find algorithm where we will, for each component, remember its root, size and, additionally, a hash map that remembers the number of times p_x appears in the component.

When we need to connect two components, the newly created component is rooted in the root of the larger component. Now we must traverse the entire smaller component (e.g. using the DFS algorithm) and correct the values in the larger component's hash map.

The time complexity of this algorithm is \mathcal O(N \log^2 N).


There are no comments at the moment.