Sakurako and a Stolen Legend#412

Sakurako and a Stolen Legend (Editorial)

Author:

Bohdan Feysa

Task preparation:

Bohdan Feysa

Editorial:

Bohdan Feysa

Block : n, m \leq 80:

We compute all SCCs in \mathcal{O}(n^3) for each of the moments of time using a simple DFS. After that, we create an array ans[i][j], 1 \leq i, j \leq n, which stores the minimal moment of time when and are in the same SCC. After that, we answer all queries in . Total time complexity: \mathcal{O}(n^3 \cdot m + q).

Block : n, m \leq 10^3:

We compute all SCCs in \mathcal{O}(n + m) for each of the moments of time using Kosaraju's algorithm. After that, we create an array ans[i][j], 1 \leq i, j \leq n, which stores the minimal moment of time when and are in the same SCC. After that, we answer all queries in . Total time complexity: \mathcal{O}((n + m) \cdot m + q).

Block : q \leq 100:

For each block, we use binary search for each query, in which we compute SCCs times in \mathcal{O}(n + m) time.

This results in a total time complexity of \mathcal{O}((n + m) \cdot q \cdot \log n).

Now we introduce offline incremental SCC algorithms which work in \mathcal{O}(m \log m) time.

Let's use the divide and conquer technique on the list of edges. We can also think about it as divide and conquer over the timeline. So, let's assume we have a function rec(a, b, edges), where is the start of the time interval, is the end (both inclusive), and edges is the list of edges along with the times when they were added. We start the process with rec(0, m-1, everything).

Each time we look at the middle of the time interval, we compute s = \left\lfloor \frac{a + b}{2} \right\rfloor. We use a standard offline algorithm to calculate SCCs in the graph consisting only of edges from edges which were added at or before . We want to split recursively while keeping good complexity.

It turns out that in the moments after , all the SCCs we just computed will stay connected. So, we can merge whole components into single vertices and only pass to the right the edges connecting different components. The edges connecting different components were useless in the past, so we pass the rest to the left. This way, each edge appears once at every level of the recurrence. There are \mathcal{O}(\log m) levels, and in each level the overall complexity is linear. Hence, we get \mathcal{O}(m \log m) complexity (assuming a careful implementation with no extra logarithmic factors).

Block : Full solution, no tests with t = 1:

First, we create an additional 2 \cdot q edges and add them to the graph. These represent the queries. We then use the offline incremental SCC algorithm to get information about every edge and whether its endpoints are in the same SCC at any moment in time. After that, we extract the answers from the additional edges that we added.

Time complexity: \mathcal{O}((m + q) \log (m + q)).

Block : Full online query solution:

We label each edge with the time when its endpoints are in the same SCC. (Cost: \mathcal{O}(m \log m)). After that, we create an undirected weighted copy of the graph, where the weights correspond to the time labels of the original edges. Then, we build a Minimum Spanning Tree (MST) using the edges of the copy. (Cost: \mathcal{O}(m \log m))

Finally, we use binary lifting (binary jumps) + LCA (Lowest Common Ancestor) to find the maximum edge weight on the path from to in the MST. (Cost: \mathcal{O}(n \log n))

Total time complexity: \mathcal{O}(m \log m + m \log m + n \log n)