Processing math: 53%

4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс


Задача E. НурлашКО

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа G, состоящий из n вершин, без ребер, во время игры игроки выполняют q операций. Операции бывают следующих типов:
  1. Добавить ориентированное ребро из вершины ui в вершину vi.
  2. Вывести xi, если существует ориентированный путь из вершины 1 в вершину xi, иначе 0.
Гарантируется, после операции граф останется ациклическим. Ациклический граф - случай ориентированного графа, в котором отсутствуют ориентированные циклы.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1<=n,q<=106,0<=t<=1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
  1. Запросы первого типа заданы в формате: 1 ai bi (0<=ai,bi<=2109).
  2. Запросы второго типа заданы в формате: 2 ai (0<=ai<=2109).
Обратите внимание, что вершины ui, vi для запросов типа 1 и вершина xi для запросов типа 2 закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: {
u_i = (a_i \oplus (t*lastans)) \mod n + 1, \quad v_i = (b_i \oplus (t*lastans)) \mod n + 1

x_i = (a_i \oplus (t*lastans)) \mod n + 1

} где lastans — последний ответ на запрос типа 2 (изначально lastans равен 0). Здесь \oplus обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как xor. Операция a \mod b означает взятие остатка от деления a на b. Гарантируется, что во входных данных присутствует хотя бы один запрос типа 2.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. Тесты из условий. Оценивается в 0 баллов.
  2. n, q <= 10^3, u_i = 1, t = 0. Оценивается в 11 баллов.
  3. n, q <= 10^3. Оценивается в 18 баллов.
  4. t = 0. Оценивается в 39 баллов.
  5. Ограничения из условия. Оценивается в 32 баллов.
Примеры:
Вход
5 9 0
2 0
2 1
1 0 1
2 1
1 2 3
1 2 3
2 3
1 1 2
2 3
Ответ
1
0
2
0
4
Вход
5 9 1
2 0
2 0
1 0 1
2 1
1 0 1
1 0 1
2 1
1 1 2
2 3
Ответ
1
0
2
0
4
( Zharaskhan Aman )
посмотреть в олимпиаде

Комментарий/решение:

пред. Правка 2   -1
5 года 3 месяца назад #

показать/скрыть код

C++

пред. Правка 2   0
5 года 3 месяца назад #

показать/скрыть код

C++

пред. Правка 2   0
5 года 2 месяца назад #

Мое решение

показать/скрыть код

C++

  0
4 года 11 месяца назад #

показать/скрыть код

C++