Editorial for Another Random Contest 1 P5 - A Strange Country

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: andy_zhu23

Subtask 1

Simply simulate the process by using Kruskal's algorithm to find the minimum spanning tree.

Time Complexity: $\mathcal O(MK)$ ~\mathcal O(MK)~

Subtask 2

Set up $K$ ~K~ disjoint set unions numbered $1$ ~1~ to $K$ ~K~. Enumerate roads from smallest to greatest by cost similar to standard Kruskal's algorithm. For every edge, binary search for the first disjoint set union such that the two cities it connects haven't been connected yet. The index of that disjoint set union is the day that this road activates. Merge the two cities in that disjoint set union afterwards.

Time Complexity: $\mathcal O(M \log K)$ ~\mathcal O(M \log K)~

Comments

There are no comments at the moment.