Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Планируется отправить экспедицию к соседней звёздной системе. Были отобраны n кандидатов, пронумерованных от 1 до n, среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.
Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для i-го кандидата является целое число ai, которое равно номеру кандидата, с которым i-й кандидат не готов отправиться в экспедицию, либо −1, если i-й кандидат готов отправиться в экспедицию в любом составе.
Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат i, и ai ≠ −1, то туда не входит кандидат ai. Организаторы хотят выбрать максимальное количество участников экспедиции.
Требуется написать программу, которая по заданным результатам опроса кандидатов определяет максимальное количество кандидатов, которых можно отправить в экспедицию.
В первой строке входных данных находится целое число n — количество кандидатов.
В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число ai.
В единственной строке выведите одно целое число — максимальное количество кандидатов, которых можно отправить в экспедицию.
1 ≤ n ≤ 300 000
ai = −1 или 1 ≤ ai ≤ n, ai ≠ i
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 19 | n ≤ 20 | полная | |
2 | 10 | a1 = −1, для i > 1 выполнено ai = i − 1 | первая ошибка | |
3 | 15 | для всех i выполнено ai < i | 2 | первая ошибка |
4 | 13 | 1 ≤ n ≤ 2000 | 1 | первая ошибка |
5 | 43 | 1 ≤ n ≤ 300 000 | 1, 2, 3, 4 | первая ошибка |
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|