| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 131 | 14 | 11 | 14.667% |
В компании работают $n$ бурундуков ($n \ge 2$), пронумерованных целыми числами от 1ドル$ до $n$. Бурундук с номером 1ドル$ является основателем компании, а каждый из остальных бурундуков имеет ровно одного непосредственного начальника. Иными словами, иерархия бурундуков представляет собой корневое дерево, где родитель вершины является её начальником, а дети вершины являются её подчинёнными. Бурундуки, имеющие подчинённых, называются менеджерами, а остальные --- консультантами. Структура компании такова, что каждый менеджер имеет не более 8ドル$ подчинённых. Обратите внимание, что основатель компании также является менеджером.
Основатель компании решил составить доклад для инвесторов о последних проделанных улучшениях разрабатываемого продукта. Каждое улучшение является результатом работы кого-то из консультантов компании. Все улучшения пронумерованы в хронологическим порядке их совершения.
Для каждого из консультантов известен список улучшений, сделанных этим консультантом. Каждый консультант обязан выбрать одно из этих улучшений и сделать о нём доклад своему менеджеру. Таким образом, доклад любого консультанта будет состоять ровно из одного улучшения.
Каждый менеджер, в том числе основатель компании, должен сделать доклад, представляющий собой объединение докладов всех его подчиненных. Для этого он берёт доклады, полученные от подчинённых, и записывает их подряд без изменений в некотором порядке. Например, если первый доклад состоит из улучшений $[1, 3],ドル а второй --- из улучшений $[2, 4, 10],ドル то в результате объединения может получиться доклад $[2, 4, 10, 1, 3],ドル либо доклад $[1, 3, 2, 4, 10],ドル никакие другие доклады получиться не могут.
Основатель компании стремится рассказать об улучшениях максимально логично, поэтому он хочет, чтобы в его докладе улучшения шли в хронологическом порядке, то есть по возрастанию номеров. Помогите консультантам выбрать, о каком улучшении они должны рассказать, а менеджерам выбрать, в каком порядке им располагать доклады подчиненных при объединении, чтобы в итоговом докладе основателя компании вошедшие в него улучшения шли в хронологическом порядке.
В первой строке содержится целое число $n$ (2ドル \leq n \leq 100,000円$) --- количество бурундуков в компании. Далее следуют $n$ описаний бурундуков, по одному в строке:
Бурундук с номером 1ドル$ (основатель компании) всегда является менеджером, а каждый из остальных бурундуков упомянут в качестве подчинённого ровно один раз и прямо или косвенно подчинен основателю компании.
Сумма чисел $m_i$ по всем консультантам не превосходит 100ドル,000円$. Гарантируется, что никакое улучшение не было сделано двумя различными консультантами, то есть все упомянутые всеми консультантами улучшения различны.
Если составить доклад требуемым образом невозможно, выведите <<No>>.
Если доклад составить возможно, выведите <<Yes>>. В этом случае затем вы можете вывести сертификат, который описывает для каждого из бурундуков в порядке их номеров следующее:
Особенность этой задачи заключается в следующем: вам разрешается как выводить сертификат, так и не выводить его. Если решение не выводит сертификат, но правильно определяет возможность составления доклада, оно получит часть баллов за тест.
Обратите внимание, что вывод некорректного сертификата приводит к вердикту <<Неправильный ответ>> и нулю баллов за этот тест, несмотря на правильность определения возможности составления доклада.
Если во всех тестах подзадачи правильно определена возможность составления доклада, а также во всех тестах, где доклад возможен, предъявлен верный сертификат, за подзадачу выставляется полный балл.
В противном случае, если во всех тестах подзадачи правильно определена возможность составления доклада, и на любой тест сертификат либо верный, либо отсутствует, за подзадачу выставляется частичный балл. Обратите внимание, что подзадачи, зависящие от неё, в таком случае будут запущены для тестирования и даже могут быть оценены в полный балл.
Обозначим за $K$ максимальное количество непосредственных подчинённых у бурундуковменеджеров, т.е. $K = \max{k_i}$. Также обозначим суммарное количество улучшений у бурундуковконсультатов за $\sum_{m_i}$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | $n, \sum m_i \leq 10,ドル $K \le 2$ |
| 2 | 6 | $n, \sum m_i \leq 20,ドル $K \le 8$ |
| 3 | 4 | $n, \sum m_i \leq 100,ドル $K \le 2$ |
| 4 | 4 | $n, \sum m_i \leq 100,ドル $K \le 5$ |
| 5 | 4 | $n, \sum m_i \leq 100,ドル $K \le 8$ |
| 6 | 4 | $n, \sum m_i \leq 500,ドル $K \le 2$ |
| 7 | 4 | $n, \sum m_i \leq 500,ドル $K \le 5$ |
| 8 | 4 | $n, \sum m_i \leq 500,ドル $K \le 8$ |
| 9 | 8 | $n, \sum m_i \leq 2000,ドル $K \le 2$ |
| 10 | 6 | $n, \sum m_i \leq 2000,ドル $K \le 5$ |
| 11 | 6 | $n, \sum m_i \leq 2000,ドル $K \le 8$ |
| 12 | 12 | $n, \sum m_i \leq 100,000円,ドル $K \le 2$ |
| 13 | 6 | $n, \sum m_i \leq 100,000円,ドル $K \le 5$ |
| 14 | 14 | $n, \sum m_i \leq 100,000円,ドル $K \le 8$ |
6 1 3 5 4 6 2 3 10 61 60 2 2 80 20 2 2 40 70 1 2 3 2 2 4 30 90 91 92
Yes 5 6 4 10 20 40 2 3 30
3 1 2 2 3 2 1 1 2 1 2
Yes 2 3 1 2
5 1 2 2 3 2 1 2 1 2 4 5 2 1 1 2 1 3
No
Во втором примере не сделан вывод сертификата, что соответствует частичному решению.
В третьем примере каждый из консультантов сделал ровно одно улучшение, поэтому выбор улучшений однозначен.
У третьего менеджера есть два возможных варианта доклада: $[1, 3]$ или $[3, 1]$.
У первого менеджера есть четыре возможных варианта доклада с учетом всех возможностей доклада третьего менеджера: $[1, 3]$ + $[2]$ = $[1, 3, 2],ドル $[2]$ + $[1, 3]$ = $[2, 1, 3],ドル $[3, 1]$ + $[2]$ = $[3, 1, 2]$ и $[2]$ + $[3, 1]$ = $[2, 3, 1],ドル но ни в одном из этих докладов улучшения не идут в хронологическом порядке.