Editorial for COCI '10 Contest 7 #5 Kuglice
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
We will solve the task using the offline approach, i.e. we will load all the input data at the beginning and then analyse it in order to find the answers to the given queries. It turns out that it's easier to solve the task if we execute queries in backwards order. Instead of removing the edges, we will be adding them.
This allows us to solve the task using a small modification of the union-find algorithm.
Comments