Задача №114898. Доклад инвесторам
В компании работают \(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\), затем следует число \(k_i\) — количество непосредственных подчинённых у этого бурундука (\(1 \le k_i \le 8\)), а затем следуют \(k_i\) различных чисел от \(2\) до \(n\) — номера бурундуков, которые являются его подчинёнными;
- если бурундук является консультантом, то описание начинается с числа \(2\), затем следует число \(m_i\) — количество улучшений, о которых этот консультант может рассказать, а затем следуют \(m_i\) различных целых чисел от \(1\) до \(100\,000\) — номера улучшений.
Бурундук с номером \(1\) (основатель компании) всегда является менеджером, а каждый из остальных бурундуков упомянут в качестве подчинённого ровно один раз и прямо или косвенно подчинен основателю компании.
Сумма чисел \(m_i\) по всем консультантам не превосходит \(100\,000\). Гарантируется, что никакое улучшение не было сделано двумя различными консультантами, то есть все упомянутые всеми консультантами улучшения различны.
Если составить доклад требуемым образом невозможно, выведите « No ».
Если доклад составить возможно, выведите « Yes ». В этом случае затем вы можете вывести сертификат , который описывает для каждого из бурундуков в порядке их номеров следующее:
-
если бурундук является менеджером, то нужно вывести список его подчиненных в том порядке, в котором требуется расположить их доклады;
- если бурундук является консультантом, то нужно вывести номер улучшения, о котором ему нужно рассказать в своем докладе.
Особенность этой задачи заключается в следующем: вам разрешается как выводить сертификат, так и не выводить его. Если решение не выводит сертификат, но правильно определяет возможность составления доклада, оно получит часть баллов за тест.
Обратите внимание, что вывод некорректного сертификата приводит к вердикту « Неправильный ответ » и нулю баллов за этот тест, несмотря на правильность определения возможности составления доклада.
Во втором примере не сделан вывод сертификата, что соответствует частичному решению.
В третьем примере каждый из консультантов сделал ровно одно улучшение, поэтому выбор улучшений однозначен.
У третьего менеджера есть два возможных варианта доклада: \([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]\), но ни в одном из этих докладов улучшения не идут в хронологическом порядке.
Если во всех тестах подзадачи правильно определена возможность составления доклада, а также во всех тестах, где доклад возможен, предъявлен верный сертификат, за подзадачу выставляется полный балл.
В противном случае, если во всех тестах подзадачи правильно определена возможность составления доклада, и на любой тест сертификат либо верный, либо отсутствует, за подзадачу выставляется частичный балл. Обратите внимание, что подзадачи, зависящие от неё, в таком случае будут запущены для тестирования и даже могут быть оценены в полный балл.
Обозначим за \(K\) максимальное количество непосредственных подчинённых у бурундуков-менеджеров, т.е. \(K = \max k_i\). Также обозначим суммарное количество улучшений у бурундуков-консультатов за \(\sum m_i\).
| Баллы | Ограничения | |||||
| Подз. | Частичные | Полные | \(n\), \(\sum m_i\) | \(K\) | Необх. подзадачи | Информация о |
| проверке | ||||||
| 1 | 9 | 18 | \(n, \sum m_i \leq 10\) | \(K \le 2\) | – | первая ошибка |
| 2 | 3 | 6 | \(n, \sum m_i \leq 20\) | \(K \le 8\) | У, 1 | первая ошибка |
| 3 | 2 | 4 | \(n, \sum m_i \leq 100\) | \(K \leq 2\) | 1 | первая ошибка |
| 4 | 2 | 4 | \(n, \sum m_i \leq 100\) | \(K \leq 5\) | У, 1, 3 | первая ошибка |
| 5 | 2 | 4 | \(n, \sum m_i \leq 100\) | \(K \le 8\) | У, 1–4 | первая ошибка |
| 6 | 2 | 4 | \(n, \sum m_i \leq 500\) | \(K \leq 2\) | 1, 3 | только баллы |
| 7 | 2 | 4 | \(n, \sum m_i \leq 500\) | \(K \leq 5\) | У, 1, 3, 4, 6 | только баллы |
| 8 | 2 | 4 | \(n, \sum m_i \leq 500\) | \(K \le 8\) | У, 1–7 | только баллы |
| 9 | 4 | 8 | \(n, \sum m_i \leq 2000\) | \(K \leq 2\) | 1, 3, 6 | только баллы |
| 10 | 3 | 6 | \(n, \sum m_i \leq 2000\) | \(K \leq 5\) | У, 1, 3, 4, 6, 7, 9 | только баллы |
| 11 | 3 | 6 | \(n, \sum m_i \leq 2000\) | \(K \le 8\) | У, 1–10 | только баллы |
| 12 | 6 | 12 | \(n, \sum m_i \leq 100\,000\) | \(K \leq 2\) | 1, 3, 6, 9 | только баллы |
| 13 | 3 | 6 | \(n, \sum m_i \leq 100\,000\) | \(K \leq 5\) | У, 1, 3, 4, 6, 7, 9, 10, 12 | |
| только баллы | ||||||
| 14 | 7 | 14 | \(n, \sum m_i \leq 100\,000\) | \(K \le 8\) | У, 1–13 | только баллы |
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