Mock CCC '22 Contest 2 J5 - Dominating the Olympics

View as PDF

Submit solution

Points: 10
Time limit: 1.5s
Java 2.5s
Python 3.5s
Memory limit: 512M

Problem types

Tommy is an all-around winter Olympian. In fact, he is so good he can participate in any event and easily win. Tommy is also a genius scientist and can clone himself infinitely to participate in multiple events at once.

There are N events at the Olympics, numbered 1 to N, and event i takes T_i minutes. Unfortunately, the organizers have come up with a plan to stop Tommy. Each event i will have R_i prerequisite events, where Tommy must complete all the prerequisite events of event i before competing in event i. The organizers may have also created these prerequisites in a loop. For example, he must do event X before event Y, event Y before event Z, and event Z before X. Since Tommy cannot bypass this, he will ignore those events.

Help Tommy find out the minimum time he can take to complete all the events he can!


1 \le N \le 5 \times 10^3

1 \le T_i \le 10^4

0 \le R_i < N

Input Specification

The first line contains one integer N, the number of events.

The next N lines begin with two space-separated integers, the i^\text{th} line containing information for event i: T_i, the time event i takes, and R_i, the number of prerequisite events event i has. R_i space-separated integers will follow, indicating the events Tommy must finish before competing in event i.

Output Specification

Output the minimum number of minutes Tommy can take to complete all the events he can.

Sample Input

30 1 3
20 0
10 2 4 5
10 0
10 0

Sample Output



Tommy can be doing events 4 and 5 at the beginning. After completing event 4 and 5 in 10 minutes, he can then do event 3. After completing event 3, after an additional 10 minutes, he can do event 1, which takes 30 minutes. This sums to 10+10+30=50 minutes. Event 2 can be done anytime in this 50 minute time frame, so it does not need to be added to the total time.


There are no comments at the moment.