- Описание
- Отправленные решения
24. D-CoV-3999
В современном мире вирусы развиваются всё быстрее и быстрее, миру приходится меняться и адаптироваться. В частности новый штамм вируса D-CoV-3999 получил удивительную мутацию и теперь передается при контакте больного со здоровым в 100% случаев.
В одной крупной компании были введены дополнительные правила безопасности: теперь каждый сотрудник работает из своего изолированного куба, чтобы предотвратить возможность заражения коллег. Но в силу специфики своей деятельности, компания не может отказаться от очных командных встреч, поэтому каждый сотрудник на входе в офис сдает экспресс ПЦР-тест, результат которого приходит в конце дня. В случае, если по результатам тестирования обнаружен зараженный, всю контактировавшую с ним группу людей выводят на карантин. Компания нуждается в вашей помощи автоматизировать этот процесс!
Вам даются результаты ПЦР-тестов всех ваших сотрудников в конце рабочего дня, а также список участников всех встреч, на которых сотрудники присутствовали. Как только сотрудник на одной из встреч пересекается с зараженным, он сам становится зараженным и теперь заражает других. По входным данным требуется определить список сотрудников, которых необходимо отправить на карантин в конце рабочего дня.
Формат ввода
В первой строке содержится одно число $n$ $(3 \le n \le 10^5)$ — количество работников.
Во второй строке содержится $n$ чисел $a_i$, количество результатов тестов в конце рабочего дня. $a_i$ равно 1 в случае, если человек болел на момент начала рабочего дня, в противном случае 0.
Далее следует n строк. Первое число $k_i$ $(0 \le k_i \le 10^5)$ равное количеству встреч, которое посетил сотрудник. Далее через пробел перечислены порядковые номера встреч $meeting_i$ $(1 \le meeting_i \le 10^9)$ — номера встреч. Чем меньше номер, тем раньше была встреча, при этом некоторые встречи могли не состояться (номеров таких встреч не будет ни у одного работника).
Гарантируется, что сумма всех $k_i$ не превышает $10^5$.
Формат вывода
Выведите ровно $n$ чисел через пробел. Если $i-ый$ работник должен быть выведен на карантин, соответствующее число должно быть равно 1 и 0 в противном случае.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
4
1 0 0 1
1 1
1 1
0
0
1 1 0 1