Editorial for CPC '21 Contest 1 P4 - AQT and Directed Graph

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

Subtask 1

For every node, run a DFS from that node to find its highest reachable node, and find the best answer out of all of those.

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

Subtask 2

The graph can be treated as undirected in this subtask, so we just need to check the top 2 nodes (by label) in each component individually. One way to do this is to find each component using DFS.

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

Subtask 3

We can use dynamic programming as the graph is a DAG. Let C_u be the list of nodes adjacent to node u, our recurrence is dp[u] = \max(u, \max_{v \in C_u} dp[v]).

Finally, the answer is now simply the lexicographically greatest pair (u, dp[u]) such that u < dp[u].

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

Subtask 4

We can rethink our strategy in subtask 1. Instead of applying our technique forwards by fixing node x, we can instead search from every possible y on the reverse graph from the greatest to least label, marking nodes that we visit with the current label. If a node was already marked previously, we can show that the answer for that node and all nodes that are reachable from it is at least as good as our current answer and can thus skip it, so we only need to visit each node once.

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


There are no comments at the moment.