Overview

Starting from mountain hut \(1\), the problem asks for the maximum number of mountain huts that can be visited while following trails such that the altitudes are strictly monotonically increasing.

Analysis

This problem is a type of “longest path problem” on a graph. In general, finding the longest path in a directed graph is known to be very computationally expensive (NP-hard). Therefore, approaches that naively explore all paths (such as simple depth-first search) will take too much computation time and result in TLE (Time Limit Exceeded).

However, this problem has a very important condition: “the altitudes of consecutively visited mountain huts must be strictly monotonically increasing (\(P_{v_i} < P_{v_{i+1}}\))”.

Due to this condition, it is impossible to move in a direction where altitude decreases or stays the same. In other words, “cycles” where you return to the same mountain hut twice can never exist. A directed graph without such cycles is called a DAG (Directed Acyclic Graph).

If the graph is a DAG, we can efficiently compute the longest path using dynamic programming (DP). Specifically, by processing mountain huts in order from lowest altitude and determining “the maximum number of mountain huts that can be visited to reach this point,” we can derive the correct answer.

Algorithm

1. Graph Construction: Among the given edges \(U \to V\), only adopt edges satisfying the condition \(P_U < P_V\) and create an adjacency list adj.

2. Vertex Sorting: To process each mountain hut in order of increasing altitude \(P_i\), create a list order by sorting vertex numbers \(1, 2, \dots, N\) in ascending order of altitude.

3. Dynamic Programming (DP) Preparation: Define the array dp[i] as “the maximum number of mountain huts visited when reaching mountain hut \(i\) starting from mountain hut \(1\)”. Initialize all values to -1 to represent unreached states, and set dp[1] = 1 for the starting point.

4. DP Update (Push DP): Process mountain huts \(u\) (elements of order) in order from lowest altitude. If dp[u] is not -1 (i.e., reachable from mountain hut \(1\)), update the values for each adjacent mountain hut \(v\) reachable from \(u\) as follows: $\(dp[v] = \max(dp[v], dp[u] + 1)\)$

5. Computing the Answer: The maximum value of dp[u] among all reachable mountain huts is the desired answer.

Complexity

• Time Complexity: \(O(N \log N + M)\)
  • Sorting vertices by altitude takes \(O(N \log N)\).
  • The DP update examines each vertex and each edge at most once, taking \(O(N + M)\).
  • Overall, this is \(O(N \log N + M)\), which runs sufficiently fast under the given constraints.
• Space Complexity: \(O(N + M)\)
  • Used for storing the graph’s adjacency list, DP array, etc.

Implementation Notes

• Edge Filtering: By ignoring edges where \(P_U \geq P_V\) at the input stage, we can reduce the number of edges in the graph and eliminate unnecessary processing.

• Reachability Check: When dp[u] is -1 (unreached), it is important to skip transitions from that point using if dp[u] != -1:.

• Python-Specific Note: It is also possible to implement this using “memoized recursion” with recursive functions for graph traversal, but in Python there is a risk of hitting the recursion depth limit (Recursion Error). By implementing “sort and push DP with loops” as done here, the solution can be computed safely and efficiently without worrying about recursion limits.

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    P = [0] * (N + 1)
    for i in range(N):
        P[i+1] = int(data[2+i])
    
    adj = [[] for _ in range(N + 1)]
    idx = 2 + N
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx+1])
        if P[u] < P[v]:
            adj[u].append(v)
        idx += 2
        
    order = sorted(range(1, N + 1), key=lambda x: P[x])
    
    dp = [-1] * (N + 1)
    dp[1] = 1
    
    ans = 1
    for u in order:
        if dp[u] != -1:
            if dp[u] > ans:
                ans = dp[u]
            nxt_dist = dp[u] + 1
            for v in adj[u]:
                if dp[v] < nxt_dist:
                    dp[v] = nxt_dist
                    
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.