D2. фанатам стратегий 3 (7 )
данный шаг отличается от предыдущего формулировкой ограничений на входные данные. перед проверкой решения с формулировкой ограничений из этого шага, убедитесь, что это решение проходит и на предыдущем шаге.
к добавлено примечание!
вскоре стало понятно, что всё совсем не просто. нельзя взять и построить здание. их в этой игре ещё и открыть нужно.
новое здание типа можно построить, только если на нашей базе функционирует хотя бы по одному новому зданию из списка необходимых зданий здания типа .
сколько на самом деле нам придётся построить зданий (не считая электростанций)? какие они? в каком порядке их строить? ваша – найти ответы на эти вопросы.
примечание
гарантируется, что существует такая последовательность постройки зданий, что здания всех типов можно построить.
формат входных данных
в первой строке записаны три целых числа n, m и t (1≤≤≤5⋅104; =1) – количество различных типов новых зданий в игре, количество новых зданий, которые нужно построить, и номер формата выходных данных.
в следующей строке записаны m названий типов зданий, разделённых пробелами – требуемые для обеспечения устойчивой обороны здания. гарантируется, что строка не содержит одинаковых типов зданий.
далее идёт блоков по 22 строки следующего вида:
в первой строке – название типа здания.
во второй – длина списка необходимых зданий для здания данного типа и сам список необходимых зданий. гарантируется, что список не содержит одинаковых типов зданий.
сумма длин списков необходимых зданий не превышает 5⋅10^4.
название каждого типа здания – это число от 11 до 10^5.
формат выходных данных
если =1, то выведите одно число – минимальное количество зданий, которые нужно построить.
если =2, то в первой строке выведите одно число – минимальное количество зданий, которое необходимо построить, а во второй – k названий зданий, которые нужно построить, в том порядке, в котором их нужно строить. если существует несколько подходящих последовательностей – выведите любую из них.
sample input:
3 1 1
1
2
0
1
2 2 3
3
0
sample output:
3
232
477
Ответы на вопрос:
ответ:
n, m, t = map(int,
x = list(map(int,
def build(name):
if name in built:
pass
elif b[a.index(name)] == ["0"]:
built.append(name)
else:
for i in b[a.index(: ]:
if i not in built:
build(i)
built.append(name)
a = []
b = []
built = []
for i in range(0, n):
a.append(
b.append(
for i in range(0, b.:
built.append(a[b.
a.pop(b.
b.pop(b.
[build(str(o)) for o in x]
print(len(built))
объяснение:
*
Популярно: Информатика
-
yadlos3818.06.2023 19:49
-
Шляпа0007.07.2022 03:21
-
ilonabagdasarya103.11.2020 21:14
-
katyusha025.10.2022 08:47
-
Kuznetsova890310.04.2021 14:31
-
ssnn70p0aegz17.05.2022 17:44
-
annaegorova404.03.2022 16:22
-
dashashirobokova14.02.2023 09:12
-
aminamamedova319.02.2022 05:21
-
annvs120.03.2021 00:53