Overview

On a route where the next station from each station is determined, find the number of stations visited when traveling from station \(1\) to station \(N\).

Analysis

In this problem, the transition from each station to the next is uniquely determined, so it seems solvable by simple simulation. That is, we start from station \(1\), follow the instructions to move to the next station, and simply count how many steps it takes to reach station \(N\).

You might worry whether a naive implementation would be fast enough if there are loops or very long paths. However, the constraints state that “station \(N\) is reachable from station \(1\),” so there will be no infinite loops along the way. Furthermore, since \(N\) is at most \(2 \times 10^5\), even if we pass through every station exactly once, it is well within the time limit.

Therefore, a straightforward simulation is the appropriate approach. By storing the transition from each station to the next in an array, and incrementing a counter while updating the current position, we can obtain the answer.

For example, if the input is as follows:

N = 5
P = [2, 3, 4, 5]

This means we simply proceed in a straight line: station 1→2→3→4→5, so the number of visited stations is 5.

Let’s look at another example:

N = 4
P = [3, 3, 4]

This means: - Station 1 → Station 3 - Station 2 → Station 3 - Station 3 → Station 4

So starting from station 1: Station 1 → Station 3 → Station 4, and the number of visited stations is 3.

As shown, we simply need to move to the next station based on the current station’s information, so no complex processing such as loops or recursion is needed.

Algorithm

1. Store the next station \(P_i\) from each station \(i\) as a list (converting to 0-indexed for easier handling).
2. Set the current position to station \(1\) (which is 0 in 0-indexed), and initialize the count of visited stations to \(1\).
3. Continue moving to the next station until the current position becomes station \(N\) (which is N-1 in 0-indexed), incrementing the count each time.
4. Output the final count.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

The time complexity is \(O(N)\) because in the worst case, we may pass through all stations. The space complexity is also \(O(N)\), since the array storing the next station information has size \(N-1\), which is \(O(N)\) ignoring constant factors.

Implementation Notes

• Station numbers are given in 1-indexed format, so converting to 0-indexed internally makes handling easier.

• The termination condition is when the current position becomes N-1 (station \(N\) in 0-indexed).

• To speed up input reading, sys.stdin.read is used.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:]))
    
    # 駅番号は1-indexedなので、P[i-1] が 駅iから次の駅を示す
    # next_station[i] = 駅i+1から次の駅 (0-indexed)
    next_station = [p - 1 for p in P]
    
    current = 0  # 駅1 (0-indexed)
    count = 1    # 駅1を含む
    
    while current != N - 1:  # 駅Nに到達するまで (N-1は0-indexed)
        current = next_station[current]
        count += 1
        
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.