Обучение сотрудников
(Время: 0,25 сек. Память: 32 Мб Сложность: 83%)
В крупной компании Алексея проводится регулярная программа обмена опытом между N сотрудниками. В начале программы каждому сотруднику назначается один конкретный коллега, которому он передаёт свои рабочие знания и опыт. Этот список назначений фиксирован: для каждого сотрудника заранее известно, кому он передаёт знания. Программа проходит по этапам.
На первом этапе перед началом обмена каждый сотрудник работает самостоятельно и применяет собственные знания. Это используется как базовое измерение эффективности.
На втором этапе каждый сотрудник передаёт знания тому человеку, который указан для него в списке назначений.
На третьем этапе каждый сотрудник взаимодействует уже с тем человеком, которому передал знания его партнёр на предыдущем этапе.
Иначе говоря, если сотрудник A передаёт знания сотруднику B, а сотрудник B передаёт знания сотруднику C, то на третьем этапе сотрудник A будет взаимодействовать с сотрудником C. И так далее на каждом следующем этапе сотрудник взаимодействует с тем человеком, которому передал знания его партнёр на предыдущем этапе. Таким образом, через несколько этапов знания могут пройти через цепочку из нескольких сотрудников.
У каждого сотрудника есть два числовых показателя. Первый показатель - способность объяснять и передавать знания. Второй показатель - способность усваивать полученную информацию. Если сотрудник A передаёт знания сотруднику B, эффективность такого взаимодействия равна способность объяснять у сотрудника A + способность усваивать у сотрудника B. Для каждого этапа программы нужно определить самое эффективное взаимодействие, которое происходит между какой-либо парой сотрудников на этом этапе. Всего проводится Q этапов обучения.
Входные данные
В первой строке входного файла INPUT.TXT содержится два натуральных числа N, Q (1 ≤ N, Q ≤ 105). Во второй строке список назначений. В третьей строке даны N целых чисел Ai. В четвертой строке даны N целых чисел Bi (0 ≤ Ai, Bi ≤ 30).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 6
5 3 1 4 2
1 3 7 9 6
8 3 5 2 4 | 12 15 11 14 12 15 |
Пояснение к примеру
В первом примере 5 сотрудников и 6 этапов. Получаем граф по списку назначений:
На первом этапе происходит базовое измерение эффективности: каждый учится сам:
1 -> 1 (1 + 8 = 9); 2 -> 2 (3 + 3 = 6); 3 -> 3 (7 + 5 = 12); 4 -> 4 (9 + 2 = 11); 5 -> 5 (6 + 4 = 10);
На втором этапе : 1 -> 5 (1 + 4 = 5); 2 -> 3 (3 + 5 = 8); 3 -> 1 (7 + 8 = 15); 4 -> 4 (9 + 2 = 11); 5 -> 2 (6 + 3 = 9);
На третьем этапе : 1 -> 2 (1 + 3 = 4); 2 -> 1 (3 + 8 = 11); 3 -> 5 (7 + 4 = 11); 4 -> 4 (9 + 2 = 11); 5 -> 3 (6 + 5 = 11);
И так далее.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
