Bulgarian OI '09 P2 - Boxen - Olympiads Online Judge

Bulgarian OI '09 P2 - Boxen

View as PDF

Submit solution

All submissions

Best submissions

Points: 12

Time limit: 0.6s

Memory limit: 32M

Problem type

2009 Bulgarian Olympiad in Informatics

The programmer Pesho is a very thrifty person. The money which he earns from website design he stores in $N$ ~N~ money boxen $(1 \le N \le 100\,000)$ ~(1 \le N \le 100\,000)~, labeled by the integers from $1$ ~1~ to $N$ ~N~. The intention of Pesho is to buy a new super-computer. In order to avoid the temptation to spend the money on rubbish, before the necessary sum is collected, he dropped all keys of the money-boxen in a random way inside the boxen themselves.

Fortunately, Pesho marked on a sheet of paper where the key for each money-box is stored. Now, the necessary money is finally collected and Pesho has to open all the money-boxen to take the money.

Unfortunately, no keys are available: Pesho must break the boxen! Pesho doesn't like breaking things, so he'd like to break as few boxen as possible. He realized that when a broken money-box contains a key of another money-box then the second money-box could be simply unlocked.

Write a program to determine the minimal number of money-boxen that have to be broken in order to collect all the stored money.

Input Specification

The program has to solve two test cases for each run. Each test case starts with a line containing the number $N$ ~N~ of money-boxen. Then $N$ ~N~ lines follow with one integer from $1$ ~1~ to $N$ ~N~ - on the $i$ ~i~^th line is the box in which the key for the $i$ ~i~^th box is stored.

Output Specification

Output the minimal number of boxen that must be broken. Separate the numbers with a space.

Sample Input

Sample Output

2 1

Explanation

In the first test case, the 4th box must be broken, because it contains its own key. Then, you can simply break the 1st box - it contains the key for box 2, which contains the key for box 3.

In the second case, you can just break box 3 to enter everything.

Comments

1

corgi commented on Dec. 5, 2020, 6:05 p.m.

I tried to use vector to store my graph, but I got WA on 4 cases. I only got AC by switching to unordered_map. Does anyone know why this happened?

1

ross_cleary commented on Dec. 5, 2020, 6:34 p.m.

You clear the vector for each test case but don't resize it. The reason using a map worked is because maps don't require you to allocate the memory locations before you access them. I would still recommend using vectors as oppose to maps since their time complexity is better.