Задачник Базовый курс EN

Водопад загрузки

Браузер загружает страницу. Ресурсы страницы пронумерованы от 1 до n: ресурс 1 — сама страница, она нужна в момент 0. О каждом другом ресурсе i браузер узнаёт из ресурса-родителя p_i (p_i < i): стиль упоминается в странице, шрифт — в стиле, данные запрашивает скрипт. Ресурс становится нужен в тот момент, когда родитель загружен целиком.

Ресурсы лежат на m серверах; ресурс i — на сервере d_i. Прежде чем что-то запросить у сервера, браузер открывает с ним соединение: найти адрес, обменяться приветствиями, договориться о шифровании. Это занимает c_d миллисекунд. Соединение с каждым сервером открывается один раз — в тот момент, когда с этого сервера впервые понадобился какой-нибудь ресурс, — и дальше по нему идут все запросы к серверу, сколько угодно одновременно. Ресурс, который стал нужен раньше, чем соединение готово, ждёт его готовности. Запрос ресурса i, отправленный в момент s, заканчивается в момент s + t_i: в t_i входят дорога туда и обратно, работа сервера и передача.

Когда загрузится последний ресурс? И когда загрузился бы, если бы все соединения были открыты заранее, к моменту 0?

Вход

В первой строке n и m (1 ≤ m ≤ n ≤ 10⁵). Во второй — c₁, …, c_m (0 ≤ c_d ≤ 1000). Дальше n строк: p_i, d_i, t_i (p₁ = 0 и 1 ≤ p_i < i для остальных, 1 ≤ d_i ≤ m, 1 ≤ t_i ≤ 10⁵).

Выход

Два числа: момент, когда загружен последний ресурс, и тот же момент при заранее открытых соединениях.

Примеры

Пример 1

Вход

8 4
120 90 150 200
0 1 60
1 1 45
1 1 70
2 3 50
1 2 80
3 1 40
1 4 30
6 2 35

Выход

425 205

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 12 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Когда открывается соединение с сервером? Когда с него понадобился первый ресурс — первый по времени. Совпадает ли он с первым по номеру?

2Идея

Без соединений задача простая: ресурс заканчивается через t_i после родителя, и раз родитель всегда с меньшим номером, хватает одного прохода по номерам. Ответ — самая длинная цепочка от страницы до листа, критический путь.

С соединениями так нельзя. Ресурс 3 может стоять в конце долгой цепочки и понадобиться через секунду, а ресурс 4 с того же сервера — сразу после страницы. Соединение откроется ради ресурса 4, но проход по номерам дойдёт до ресурса 3 первым и откроет его на секунду позже, чем на самом деле. Поэтому моменты, когда ресурсы становятся нужны, надо разбирать по времени — как события в алгоритме Дейкстры: в куче лежат пары «момент, ресурс», и всегда достаём самый ранний.

3Разбор

Кладём в кучу (0, 1). Достали (τ, i): если с сервером d_i соединения ещё нет, оно начинает открываться сейчас и будет готово к τ + c_d. Запрос уходит в момент max(τ, готовность соединения) и заканчивается через t_i; в этот момент становятся нужны все дети i — кладём их в кучу. Ответ — самый поздний конец.

Почему порядок по времени верен: дети становятся нужны не раньше родителя, поэтому, когда из кучи достаётся событие τ, все события раньше τ уже разобраны. Значит, если соединения с сервером ещё нет, то никто раньше τ его не просил, и открыть его в τ — правильно. Ничьи по времени ни на что не влияют.

В примере страница с сервера 1 готова к 180 мс: 120 уходит на соединение. Шрифт с сервера 3 находится в стиле и заканчивается последним, в 425 мс. Если бы все соединения были открыты заранее, хватило бы 205 мс: больше половины времени загрузки — приветствия с четырьмя серверами. Поэтому сайты пишут в странице подсказку <link rel="preconnect"> — открыть соединение со шрифтовым сервером, не дожидаясь стиля, — и держат ресурсы на меньшем числе серверов.

3+Решение

4Сложность

Каждый ресурс один раз попадает в кучу: O(n log n). Ответ без соединений — O(n) одним проходом.

5Типичные ошибки

Проход по номерам. Открывает соединение ради первого по номеру ресурса сервера, а не первого по времени: ответ получается позже настоящего. Третий и четвёртый тесты построены именно так.
Соединение на каждый запрос. Его открывают один раз на сервер; ресурсы, нужные после готовности соединения, уже не ждут.
Рекурсивный обход. В восьмом тесте цепочка из 10⁵ ресурсов: рекурсия в Python упрётся в ограничение глубины.
32-битные числа. На той же цепочке время доходит до 10¹⁰ мс: в C++ и Java нужен 64-битный тип.

Алгоритмы задачи

TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи GRA Алгоритм Алгоритм Дейкстры Кратчайшие пути от одной вершины во взвешенном графе без отрицательных рёбер. O((V + E) log V) 3 задачи