Editorial for Wesley's Anger Contest 4 Problem 7 - Squirrel Cities

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

You may recognize similarities with the problem Enchanted Forest from the 2014 Chinese National Olympiad in Informatics.

Subtask 1

For the first subtask, we can construct a graph for each query using only edges with d_i \ge x_j and t_i \le y_j, and determining if the graph is connected. This can be done in many ways such as breadth first search, depth first search, or the Union-Find data structure.

Time Complexity: \mathcal{O}(Q \cdot (N + M)) or \mathcal{O}(Q \cdot (N + M \cdot \alpha(N)))

Subtask 2

For the second subtask, we can make the observation that for each unique value of d_i, there will be a minimum value of y_j where the graph is completely connected. In fact, as d_i decreases, the minimum value of y_j decreases. In order to find this minimum value of y_j for each d_i, we need to find a minimum bottleneck spanning tree, which can be done by constructing a minimum spanning tree with all edges with a durability of at least d_i, where the weight of each edge is t_i. The minimum value of y_j is equal to the maximum value of t_i in the minimum spanning tree (assuming a tree exists). If the edges are presorted by t_i, this can be done in \mathcal{O}(N + M \cdot \alpha(N)) time using Kruskal's algorithm. To answer the queries, we can binary search for the smallest value d_i where d_i \ge x_j and use the precomputed answer for that value. Alternatively, a two pointer approach can be used the answer the queries offline.

Time Complexity: \mathcal{O}(M \cdot (N + M \cdot \alpha(N)) + Q \log M)

Subtask 3

When edges are being added to the graph in decreasing order of d_i, we can maintain the minimum spanning tree efficiently. When an edge is added to the previous minimum spanning tree, it will create some cycle. If the edge with the maximum edge weight is deleted from this cycle, then we will obtain the new minimum spanning tree. We can find this edge using a Link-Cut Tree with N + M nodes where the value of the first N nodes are -\infty and the value of the (N + i)^{th} node is t_i representing the i^{th} edge (we can imagine this as a node in the middle of an edge). We can query for the maximum edge using this data structure, while also maintaining a set of the edge weights in the minimum spanning tree in order to answer queries in a similar manner as subtask 2.

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

There exist other solutions such as square root decomposition, and divide and conquer.


There are no comments at the moment.