Editorial for DMOPC '21 Contest 9 P3 - Terrible Trains

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: 4fecta

Subtask 1

For each query, create N 2-D points (D_{i, S}, D_{i, U}) and N 2-D points (D_{i, T}, D_{i, V}), where D_{a, b} is the shortest distance from a to b. Then, we need to find two points (x_1, y_1) and (x_2, y_2), one from each set, so that x_1 + x_2 + 1 \le X and y_1 + y_2 + 1 \le Y. For each point in the first set, the set of valid points in the second set forms a rectangular shape in the 2-D plane. Thus, this problem is equivalent to checking whether there is any intersection between a set of N points and N rectangles, which can be done with line sweep.

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

Subtask 2

Firstly, if D_{S, T} \le X or D_{U, V} \le Y, then it is automatically possible — simply add the new edge between the two stations that are not yet close enough (if they exist). Otherwise, the key observation is that it is always optimal for the endpoints of the additional edge to lie on the shortest path from S to U and the shortest path from T to V, possibly with U and V swapped. After all, if the endpoints do not lie on these shortest paths, they can always be pulled towards them without increasing any of the relevant distances. Secondly, given this fact, note that it is necessary for D_{S, U} + 1 + D_{T, V} + 1 \le X + Y. It turns out that this is also sufficient: the endpoints can be walked along the shortest paths towards the pair of stations that is too far, keeping the left side of the inequality constant while decreasing the distance between the further pair. Since this decrease occurs smoothly and continuously, the closer pair will not suddenly become too far. Thus, each query can be answered in \mathcal{O}(1) time.

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


There are no comments at the moment.