PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
MEDIUM
PREREQUISITES:
PARALLEL BINARY SEARCH, DISJOINT SET UNION
PROBLEM:
You have a graph. On some days, roads are destroyed. On some days, some people in some vertices are killed. Happiness of a student is the number of students in its connected component. For each query (u, v), find the maximum day such that the total happiness of student u and v is still at least V.
EXPLANATION:
First, a naive solution is to solve each query independently. Instead of destroying roads and killing students, we reverse the entire process and add students and roads instead. Now, with a fixed v as target, we can use DSU to perform the updates in reverse and find the first day where the two students in the query has total happiness \ge V. This solution works in O(n\alpha n) per query.
Now, we need to find a way to not reconstruct the DSU every query. We’ll use a technique called parallel binary search. There’s a tutorial of it here. Once you understand how it works, it’s very easy to relate it here. Instead of using a segment tree as in the article, we just replace it with a DSU instead. You can refer to the sample solutions for how to implement it for this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.