시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 20 | 5 | 5 | 25.000% |
Планируется отправить экспедицию к соседней звёздной системе. Были отобраны n кандидатов, пронумерованных от 1 до n, среди которых необходимо выбрать участников экспедиции. Организаторы хотят отправить в экспедицию как можно больше кандидатов.
Среди кандидатов был проведён опрос, в процессе которого каждый мог указать не более, чем одного из остальных кандидатов, с которым он не готов отправиться в экспедицию. Результатом опроса для i-го кандидата является целое число ai , которое равно номеру кандидата, с которым i-й кандидат не готов отправиться в экспедицию, либо −1, если i-й кандидат готов отправиться в экспедицию в любом составе.
Теперь организаторы должны выбрать, кто из кандидатов отправится в экспедицию. Решено было выбрать участников экспедиции так, что если туда входит некоторый кандидат i, и ai ≠ −1, то туда не входит кандидат ai. Организаторы хотят выбрать максимальное количество участников экспедиции.
Требуется написать программу, которая по заданным результатам опроса кандидатов определяет максимальное количество кандидатов, которых можно отправить в экспедицию.
В первой строке входных данных находится целое число n — количество кандидатов (1 ⩽ n ⩽ 300 000).
В следующих n строках даны результаты опроса, i-я из этих строк содержит результат опроса i-го кандидата, целое число ai (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 |
4 | 13 | 1 ⩽ n ⩽ 2000 |
5 | 43 | 1 ⩽ n ⩽ 300 000 |
4 2 4 2 1
2
3 2 -1 2
2
Olympiad > Russian Olympiad in Informatics > Russian Olympiad in Informatics Regional > Russian Olympiad in Informatics Regional 2019 7번