← All solutions

Solved by 20 teams.

First solved after 113 minutes.

Shortest judge solution: 1250 bytes.

It is slightly easier to count ordered pairs (u, v) which are connected, where u and v are not necessarily distinct; let us call this the “score”. It is simple to convert the score into the desired output.

Consider a graph in which each city corresponds to two vertices: one for the morning and one for the afternoon. Adding a courier connects two of these vertices. Naturally, we will want to track the components of this graph. For each component we will track how many cities it reaches. This can be done efficiently using small-into-large merging when connecting two components.

At first glance it may seem the score is simply the sum of squares of the sizes (in cities) of the components. However, this can lead to double-counting if, say, one component reaches the morning vertices for cities A and B, and another component reaches the afternoon vertices of the same cities. Let the “signature” of a city be the unordered set of component IDs for its two vertices. A pair (u, v) will be double-counted if u and v have the same signature and the signature contains two different components. So as we merge components, we need to incrementally update a frequency table of signatures as well as the sum of squares of component sizes.

Assuming a balanced tree is used for the signature frequency table, running time will be O(m log² n).