қазақша
русскийОбластная олимпиада по информатике 2016-2017
В стране T K − Robots есть $n$ городов. Для удобство пронумеруем их от 1 до n. Из каждого города выходит ровна одно односторонняя дорога. Из i - го города в город $p_i$. В начале в городе i находится $a_i$ роботов. Роботы очень любят путешествовать по стране. За один момент времени, робот находящиеся в городе i пойдет в город $p_i$. Найдите максимальное количество роботов, которые одновременно будут в одном городе.
Во второй строке находятся n целых числа $p_1, p_2, ..., pn$ ($1 ≤ pi ≤ n$) и $p_i ̸= i$.
В третьей строке находятся n целых числа $a1, a2, ..., an$ ($0 ≤ ai ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.
В 20% тестовых данных: 2 ≤ n ≤ 2000.
В 20% тестовых данных: 2 ≤ n ≤ 105, а также выполняются следующие условия:
посмотреть в олимпиаде
Входные данные
В первой строке входных данных находится одно целое число $n$($2 ≤ n ≤ 10^5$) - количество городов.Во второй строке находятся n целых числа $p_1, p_2, ..., pn$ ($1 ≤ pi ≤ n$) и $p_i ̸= i$.
В третьей строке находятся n целых числа $a1, a2, ..., an$ ($0 ≤ ai ≤ 10^9$), где $a_i$ - количество роботов в i-ом городе.
Выходные данные
Выведите одно целое число — максимальное возможное количество роботов, которые будут находиться в одном городе одновременно.Примеры:
Вход:3 2 3 1 5 4 8Ответ:
8Вход:
5 5 3 4 2 1 7 6 0 3 3Ответ:
7Вход:
7 7 1 1 3 3 7 4 3 1 4 0 2 0 2Ответ:
5Вход:
12 11 1 6 1 7 8 8 7 7 9 12 11 12 29 7 19 4 8 39 31 22 34 25 40Ответ:
81Вход:
10 2 1 1 1 3 4 3 6 7 8 2 3 1 4 0 5 1 1 3 0Ответ:
12
Оценивание:
В 8% тестовых данных: $2 ≤ n ≤ 10^5$ , и $p_1, p_2, ..., p_n$ - является перестановкой чисел 1, 2, .., n.В 20% тестовых данных: 2 ≤ n ≤ 2000.
В 20% тестовых данных: 2 ≤ n ≤ 105, а также выполняются следующие условия:
- a) p1 = 2, p2 = 1 b) Из любого города можно добраться в город с номером 1. В остальных ограничения из условия.
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.