CCCHK '15 S4 - When to meet?

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

A maze consists of N rooms and N one-way corridors. From the i-th room there is exactly one one-way corridor to the k[i]-th room.

An adventurer and a minotaur are in the maze. The adventurer will move from a room to the next room in one minute, while the minotaur will do the same in two minutes. The maze is constructed so that as long as the adventurer and the minotaur start moving at the same moment, they will eventually meet in the same room.

The adventurer and the minotaur choose two different rooms in the maze at the very beginning. After that, they will keep moving from one room to another room via the corridors. You are asked the maximum possible time for the adventurer and the minotaur to meet exactly in a room.

Input specification:

The first line contains an integer N, the number of rooms.

The second line contains N numbers, of which the i-th number is k[i].

  • In 50\% of the test cases, 1 \leq N \leq 5000;
  • In 100\% of the test cases, 1 \leq N \leq 100000.

Output specification:

The maximum possible time for the adventurer and the minotaur to meet in a room.

Sample Input 1

6
2 3 4 5 6 1

Sample Output 1

10

Sample Input 2

6
2 3 4 5 3 4

Sample Output 2

8

Explanation:

In the second sample, if the adventurer starts at room 6 and the minotaur starts at room 1, they need 8 minutes to meet at the same room (i.e., room 5).


Comments

There are no comments at the moment.