Editorial for CTU Open Contest 2018 - Escalators

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.

Split the problem into $20$ ~20~ instances by bits.
In $i^\text{th}$ ~i^\text{th}~ iteration, consider only nodes which have $1$ ~1~ on the $i^\text{th}$ ~i^\text{th}~ bit.
Find sizes of components of ones (DFS).
Each component adds $\binom{\text{size}}{2} \times 2^i$ ~\binom{\text{size}}{2} \times 2^i~.

Complexity $\mathcal O(N \log W)$ ~\mathcal O(N \log W)~

Comments

There are no comments at the moment.