Editorial for DMOPC '17 Contest 5 P5 - XOR Bridges - Olympiads Online Judge

Editorial for DMOPC '17 Contest 5 P5 - XOR Bridges

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.

Author: r3mark

For the first two subtasks, the constraints are low enough that finding all edges and DFSing for each query passes.

Time Complexity: $\mathcal O(N^2+QN)$ $O (N^{2} + Q N)$

For subtask 3, observe that the last $k$ $k$ bits (where $M=2^k-1$ $M = 2^{k} - 1$ ) of all the node values don't matter since $M$ $M$ is the largest number using only the last $k$ $k$ bits. It is not hard to see that two nodes are connected if and only if their values ignoring the last $k$ $k$ bits are equal.

Time Complexity: $\mathcal O(N+Q)$ $O (N + Q)$

For the final subtask, we use disjoint sets. Consider the largest bit any value or $M$ $M$ has. Split the nodes we have into two groups, the ones with this bit and the ones without. If $M$ $M$ does not have this bit, then no nodes in one group can ever union with nodes in the other group. So we then repeat this process for the next bit with each of the two groups. If this bit is $1$ $1$ for $M$ $M$ , then any two nodes which have the same state for this bit can union. So we union all the ones in the same group. Then, we repeat this process for the next bit with the entire group. This process can be done by recursively calling a function which takes the index of the current bit being considered and an array containing the appropriate nodes. Remember to union everyone if the index of the current bit ever hits $-1$ $- 1$ .

Time Complexity: $\mathcal O(N\log M+Q)$ $O (N \log M + Q)$

Comments

There are no comments at the moment.