Overview

When traversing one-way mountain trails such that the elevation always increases, find the maximum number of mountain huts that can be visited starting from mountain hut \(1\) (i.e., the longest path length).

Analysis

In a “good traverse,” the elevations of consecutive mountain huts must satisfy \(P_{v_i} < P_{v_{i+1}}\). In other words, the only trails that can actually be used are edges going from lower elevation to higher elevation.

The key observations are as follows:

• Since all elevations \(P_i\) are distinct, if we keep only the usable edges (where \(P_u < P_v\)), we can only travel in the direction of increasing elevation.
• Therefore, this graph contains no cycles (since elevation keeps increasing, we can never return to the same vertex). In other words, it becomes a DAG (Directed Acyclic Graph).
• The problem reduces to finding the “longest path starting from mountain hut 1” on this DAG.

A naive DFS that “explores all possible paths” would not work for \(N, M \le 2 \times 10^5\), as the number of paths can grow exponentially (TLE). Instead, the longest path on a DAG can be computed in linear time by performing DP in topological order (here, ascending order of elevation).

Algorithm

1. For each input edge \((U_j, V_j)\), keep only those satisfying \(P_{U_j} < P_{V_j}\) and build the adjacency list adj
   • Edges not satisfying the condition can never be used in a “good traverse,” so they can be discarded
2. Create an ordering order of mountain huts sorted by ascending elevation (this serves as the topological order of the DAG)
3. Define the DP
   • dp[v] = the maximum number of huts visited in a “good traverse” starting from mountain hut \(1\) and ending at mountain hut \(v\) (0 if unreachable)
   • Initial value: dp[0] = 1 (there exists a traverse consisting of only mountain hut 1); all others are 0
4. Process each vertex \(u\) in the order given by order, and perform transitions along edges \(u \to v\)
   • If dp[u] = L, then update dp[v] with max(dp[v], L + 1)
5. The maximum value in the DP array is the answer

(Illustrative example) Since we process vertices in ascending order of elevation, by the time we process \(u\), the optimal value for “reaching \(u\)” is already finalized, and we can propagate that value to vertices with higher elevation.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  • \(O(N\log N)\) for sorting by elevation, and \(O(M)\) for DP transitions (at most once per edge)
• Space complexity: \(O(N+M)\)
  • For the adjacency list and the DP array

Implementation Notes

• Keep only usable edges: There is no need to store all input edges; filter with something like if P[u] < P[v]: adj[u].append(v) (this creates the DAG and reduces unnecessary transitions).

• Handling unreachable vertices: Vertices with dp[u] == 0 are unreachable from mountain hut 1, so skipping them improves efficiency.

• Be careful with initial values: According to the problem statement, \(k=1\) (only mountain hut 1) is allowed, so dp[0]=1 and the initial answer value should also be 1.

• Since the input is large, it is safe to use sys.stdin.buffer.read() for fast input reading.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    P = [int(next(it)) for _ in range(N)]

    adj = [[] for _ in range(N)]
    for _ in range(M):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        if P[u] < P[v]:
            adj[u].append(v)

    order = sorted(range(N), key=lambda i: P[i])

    dp = [0] * N
    dp[0] = 1
    ans = 1

    for u in order:
        du = dp[u]
        if du == 0:
            continue
        ndu = du + 1
        for v in adj[u]:
            if dp[v] < ndu:
                dp[v] = ndu
                if ndu > ans:
                    ans = ndu

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.