4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс
Задача E. НурлашКО
Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт
АланашКО и НурлашКО играют с графом, и им нужна Ваша помощь. Игра начинается с ориентированного ациклического графа G, состоящий из n вершин, без ребер, во время игры игроки выполняют q операций. Операции бывают следующих типов:
- Добавить ориентированное ребро из вершины ui в вершину vi.
- Вывести xi, если существует ориентированный путь из вершины 1 в вершину xi, иначе 0.
Формат входного файла
Первая строка входных данных содержит три целых числа n, q и t (1<=n,q<=106,0<=t<=1) — количество вершин, количество операций и константное число. Каждая из следующих q строк содержит описание одного запроса.
- Запросы первого типа заданы в формате: 1 ai bi (0<=ai,bi<=2⋅109).
- Запросы второго типа заданы в формате: 2 ai (0<=ai<=2⋅109).
ui=(ai⊕(t∗lastans))modn+1,vi=(bi⊕(t∗lastans))modn+1
xi=(ai⊕(t∗lastans))modn+1
} где lastans — последний ответ на запрос типа 2 (изначально lastans равен 0). Здесь ⊕ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как ^, в Pascal — как xor. Операция amodb означает взятие остатка от деления a на b. Гарантируется, что во входных данных присутствует хотя бы один запрос типа 2.
Формат выходного файла
Для каждого запроса второго типа выведите ответ в отдельной строке.
Система оценки
Данная задача содержит 5 подзадач, в каждой подзадаче выполняются ограничения из условий:
- Тесты из условий. Оценивается в 0 баллов.
- n,q<=103, ui=1, t=0. Оценивается в 11 баллов.
- n,q<=103. Оценивается в 18 баллов.
- t=0. Оценивается в 39 баллов.
- Ограничения из условия. Оценивается в 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 )
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.