2016-17 Woburn Challenge Finals Round - Senior Division

Problem 4: Bug Infestation

Having fortunately gotten wind of the Cow-Bot's construction before meeting it in battle, the monkeys are in the process of frantically creating a virus, with the hopes of installing it into the robot and shutting it down! They've finished writing their program, which consists of N (1 ≤ N ≤ 300,000) lines of code, but unfortunately its quality may be somewhat lacking...

At any point in time, each line of code either contains a bug, or doesn't. Initially, each line i contains a bug if B_i = 1, and otherwise doesn't if B_i = 0 (0 ≤ B_i ≤ 1).

Each minute, the monkeys can select one line of code which contains a bug, and fix that bug! Unfortunately, their code is so fragile that fixing some bugs may introduce others. If a bug is fixed on line i, then if L_i = 0, there are no consequences. Otherwise, one other line L_i (1 ≤ L_i ≤ N, L_i ≠ i) will begin to have a bug (regardless of whether it already had one or not).

In order to efficiently proceed with making their viral code as correct as possible, the monkeys are interested in the answers to two questions. Firstly, what's the minumum possible number of lines of code which can be left containing bugs after they fix as many bugs as they'd like to? And secondly, how quickly can that minimum number of outstanding bugs be achieved? If Q = 1, then you only need to answer the first of these questions, and if Q = 2, then you must answer both.

In test cases worth 5/30 of the points, Q = 1 and N ≤ 2000.
In test cases worth another 4/30 of the points, Q = 1.
In test cases worth another 6/30 of the points, N ≤ 2000.

Input Format

The first line of input consists of two space-separated integers N and Q.
N lines follow, the i-th of which consists of two integers B_i and L_i (for i = 1..N).

Output Format

If Q = 1, then output a single integer – the minimum possible number of bugs which can remain in the code.
Otherwise if Q = 2, then output two space-separated integers – the minimum possible number of bugs which can remain in the code, and the minimum number of minutes required to achieve that number of bugs.

Sample Input

10 2
1 4
0 0
0 8
0 10
0 0
1 0
1 4
1 4
1 5
0 7

Sample Output

1 6

Sample Explanation

One optimal sequence of lines to debug is: 1, 6, 7, 8, 9, 5.
After this sequence, the only line containing a bug will be line 4. It's impossible to eliminate all of the bugs from the monkeys' code (hopefully the same isn't true for yours…).

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: May 07, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

As pointed out by kobortor, there was unfortunately an error in the test data used during the competition. The data has since been corrected, and submissions have been rejudged accordingly. We apologize for this issue.

This does affect the results of the competition in some unknown fashion, as Thornhill1 actually solved this problem correctly while the remaining teams did not. We've decided to leave the official results unchanged, but award Thornhill1 the equivalent of the 1st place's prize money.