COCI '22 Contest 2 #1 Tramvaji

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

One magical night Patrik and Josip were talking about the number 42 and the meaning of life. They were interrupted by the famous lady voice in the tram: The next stop is Jordanovac. Patrik and Josip were distracted by this common sentence and started discussing:

Patrik: It is a very short ride between Joranovac and Maksimir, isn't it?

Josip: It is, but the ride between Mašićeva and Kvatrić is way shorter.

Patrik: Really? I disagree.

Josip: I wonder, which is the shortest ride between all stations?

Paula, a big public traffic transport, was carefully listening to their conversation. The problem of finding the shortest ride interested her so much that she stayed in the tram longer than she intended just to listen to their conversation.

At each station (except for the first one, when they entered the tram), one of the following two things happened:

  • Patrik said: t minutes have passed since we entered the tram
  • Josip said: From station y to this station t minutes have passed

But before Paula could hear their conclusion about which ride was the shortest, they left the tram! Luckily, Paula remembers all their statements. Now she needs your help! Help her find the duration of the shortest ride and between which two stations the tram drove on that ride.

Input Specification

The first line contains the integer n (2 \le n \le 1\,000), the number of tram stations.

The i-th of the following n-1 lines contains the information about station i+1 in one of the following formats:

  • Patrik t_i – Duration of the ride between station 1 and station i+1 is t_i (1 \le t_i \le 10^9)
  • Josip y_i t_i – Duration of the ride between station y and station i+1 is t_i (y_i < i+1, 1 \le t_i \le 10^9)

Every station will be in a distinct position.

Output Specification

In one line, output three numbers: t, x_1, x_2, the duration of the shortest ride and the indices of the starting and ending stations of that ride.

If multiple solutions exist, print the one with the smallest indices of the stations.


Subtask Points Constraints
1 12 t_i \le 1\,000
2 13 Every sentence was said by Patrik.
3 25 No additional constraints.

Sample Input 1

Patrik 3
Patrik 5
Josip 1 7

Sample Output 1

2 2 3

Explanation for Sample Output 1

The tram drove for 3 minutes from the first to the second station and 5 from the first to the third. We can conclude that from the second to the third station, it took 2 minutes, which is the shortest ride.

Sample Input 2

Josip 1 5

Sample Output 2

5 1 2

Sample Input 3

Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

Sample Output 3

2 3 4

Explanation for Sample Output 3

The ride between the fourth and fifth station is also 2 minutes but because they have greater indices, only the 2 3 4 solution is accepted.


There are no comments at the moment.