Олимпиадный тренинг

Задача . C. Освещение префиксов


Задача

Темы: графы поиск в глубину и подобное снм *2400

В линию было расположено \(n\) ламп, пронумерованных целыми числами от \(1\) до \(n\). Каждая лампа изначально либо выключена (\(0\)) или включена (\(1\)).

Вам дано \(k\) подмножеств \(A_1, \ldots, A_k\) множества ламп \(\{1, 2, \dots, n\}\), таких что пересечение любых трех подмножеств пусто. Другими словами, для всех \(1 \le i_1 < i_2 < i_3 \le k\) выполнено \(A_{i_1} \cap A_{i_2} \cap A_{i_3} = \varnothing\).

За одну операцию вы можете выбрать одно из этих \(k\) подмножеств и изменить состояние всех ламп из этого подмножества (выключенные лампы становятся включенными, включенные становятся выключенными). Гарантируется, что для данных подмножеств можно совершить несколько операций так, чтобы все лампы стали включенными.

Обозначим за \(m_i\) минимальное количество операций, которое вы должны совершить, чтобы первые \(i\) ламп оказались включенными. Обратите внимание, что при этом состояние других ламп (с номерами между \(i+1\) и \(n\)) может быть любым.

Посчитайте \(m_i\) для всех \(1 \le i \le n\).

Входные данные

В первой строке находится два целых числа \(n\) и \(k\) (\(1 \le n, k \le 3 \cdot 10^5\)).

Во второй строке находится двоичная строка длины \(n\), обозначающая начальное состояние каждой лампы (лампа \(i\) выключена, если \(s_i = 0\), включена, если \(s_i = 1\)).

Описание каждого из \(k\) подмножеств следует, в следующем формате:

В первой строке описания находится единственное целое число \(c\) (\(1 \le c \le n\))  — количество элементов в подмножестве.

Во второй строке описания находится \(c\) различных целых чисел \(x_1, \ldots, x_c\) (\(1 \le x_i \le n\))  — элементы подмножества.

Гарантируется, что:

  • Пересечение любых трех подмножеств пусто;
  • С помощью нескольких операций можно сделать все лампы одновременно включенными.
Выходные данные

Вы должны вывести \(n\) строк. В \(i\)-й строке должно содержаться единственное целое число \(m_i\)  — минимальное количество операций, необходимое для того чтобы сделать все лампы с номерами от \(1\) до \(i\) включенными.

Примечание

В первом тесте:

  • Для \(i = 1\), мы можем сделать одну операцию с множеством \(A_1\), итоговые состояния будут \(1010110\);
  • Для \(i = 2\), мы можем сделать операции с множествами \(A_1\) и \(A_3\), итоговые состояния будут \(1100110\);
  • For \(i \ge 3\), we can apply operations on \(A_1\), \(A_2\) and \(A_3\), the final states will be \(1111111\).

Во втором тесте:

  • Для \(i \le 6\), мы можем просто сделать одну операцию с множеством \(A_2\), итоговые состояния будут \(11111101\);
  • Для \(i \ge 7\), мы можем сделать операции с множествами \(A_1, A_3, A_4, A_6\), итоговые состояния будут \(11111111\).

Примеры
№Входные данныеВыходные данные
1 7 3
0011100
3
1 4 6
3
3 4 7
2
2 3 
1
2
3
3
3
3
3
2 8 6
00110011
3
1 3 8
5
1 2 5 6 7
2
6 8
2
3 5
2
4 7
1
2 
1
1
1
1
1
1
4
4
3 5 3
00011
3
1 2 3
1
4
3
3 4 5 
1
1
1
1
1
4 19 5
1001001001100000110
2
2 3
2
5 6
2
8 9
5
12 13 14 15 16
1
19 
0
1
1
1
2
2
2
3
3
3
3
4
4
4
4
4
4
4
5

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет