| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 9 | 5 | 5 | 55.556% |
Давайте на минуту представим, что было бы, если бы Заун получил свою независимость от Пилтовера. Как для около-индустриального квартала, в первую очередь для Зауна было бы важно наладить быстрое транспортное сообщение между различными производственными точками.
Был создан план, в рамках которого в Зауне последовательно строятся $n$ железнодорожных линий. Сначала будет открыта первая линия, затем, спустя время, вторая, и так далее. Линии могут пересекаться (возможно, не один раз). Если линии $i$ и $j$ пересекаются, то в этом месте транспорт может переезжать с $i$-й ветки на $j$-ю или наоборот.
Также известно, что в течение дня по $i$-й линии (если она уже построена) будут курсировать ровно $a_i$ поездов. А по ночам жизнь в квартале замирает, и все поезда должны находиться в депо (не обязательно на своей ветке). В депо вместимости $A$ могут находиться не более $A$ поездов. Каждый поезд может быть размещен в любом достижимом депо (таким образом, если в депо на линии $j$ есть место, и ветки $i$ и $j$ пересекаются, то поезд, курсирующий днем по ветке $i,ドル может ночью расположиться в депо на ветке $j$).
Можно построить произвольное количество депо любой вместимости на любых ветках еще до их официального открытия. Ваша цель --- чтобы в любой момент времени все поезда на открытых ветках можно было разместить в достижимых депо. А поскольку постройка депо очень трудозатратна, хочется минимизировать их суммарную вместимость, а при равенстве --- минимизировать их количество.
Найдите $k$ --- минимальное количество депо минимальной суммарной вместимости, которое необходимо построить, чтобы открывать линии в запланированном порядке. Про каждое из $k$ депо укажите на какой из линий оно должно быть построено и какую вместимость должно иметь. Обратите внимание, что следует минимизировать суммарную вместимость, а среди таких вариантов уже выбрать с минимальным количеством.
В первой строке ввода дано целое число $n$ --- количество линий, которое планируется построить (1ドル \leqslant n \leqslant 10^6$).
В каждой из следующих 2ドル \cdot n$ строк содержится описание запросов в формате, описанном ниже.
В первой строке описания $i$-й линии записано единственное целое число $a_i$ --- количество поездов на этой линии $(1 \leqslant a_i \leqslant 10^6)$. Во второй строке описания запроса сначала дано целое число $c_i$ --- количество уже построенных линий, пересекаемых данной, $(0 \leqslant c_i \leqslant 2 \cdot 10^6$), а затем через пробел перечислены $c_i$ целых чисел --- номера линий, с которыми пересекается новая. Гарантируется, что для всех перечисленных $t$ выполняется 1ドル \leqslant t < i$.
Гарантируется, что сумма $c_i$ по всем $i$ не превосходит 2ドル \cdot 10^6$.
В первой строке выведите единственное целое число $k$ --- количество депо, которые вы собираетесь построить.
В $i$-й из следующих $k$ строк выведите через пробел по два числа: номер линии (от 1ドル$ до $n$) и вместимость $i$-го депо.
7 20 0 10 0 30 0 40 0 10 2 1 4 40 2 2 3 50 1 2
4 1 20 2 10 3 120 4 50