Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Сдать решение задачи C-Описание карты
- Полный балл: 40
- Бонусные баллы:
- Ограничение времени: 2 с
- Ограничение памяти: 256M
- Описание карты
- В давние времена карт почти не было, поэтому о возможности проехать из одного города в другой можно было узнать только из описаний других путешественников.
- Всего было известно о существовании N городов, занумерованных числами от 1 до N. Сначала о существовании путей о дорогах между городами не было известно ничего, затем стали приходить отчёты от путшественников о возможности или невозможности добраться от одного города до другого, а также запросы о возможности или невозможности добраться от одного города до другого. Все дороги двусторонние, то есть если от одного города возможно (или невозможно) добраться до второго, то и от второго возможно (или невозможно) добраться до первого.
- Помогите ученым, исследующим дорожную сеть давних времен, ответить на запросы. Запросы следует обрабатывать в том порядке, как они задавались, используя только имеющуюся на момент запроса информацию. Дорожная сеть в процессе работы не менялась, отчёты путешественников не содержат противоречий.
- Формат входных данных
- В первой строке входных данных задаётся два числа: N и K (1 ≤ N, K ≤ 100000) — количество городов и запросов.
- В каждой из следующих K строк записан запрос одного из трех типов:
- + i j — существует путь по дорогам из города i в город j
- - i j — не существует пути по дорогам из города i в город j
- ? i j — определить, существует ли путь по дорогам из города i в город j.
- Формат результата
- На каждый запрос о существовании пути по дорогам выведите одну из трёх строк:
- + — если путь существует
- - — если пути не существует
- ? — если по имеющимся на момент запроса отчётам нельзя точно определить существует или не существует путь между городами
- Примеры
- Входные данные
- 3 4
- + 1 2
- ? 1 3
- + 3 2
- ? 1 3
- Результат работы
- ?
- +
- Входные данные
- 4 5
- + 1 2
- + 3 4
- - 1 4
- ? 2 4
- ? 1 3
- Результат работы
- -
- -
- Примечания
- Система оценки: Решения, верно работающие при 1 ≤ N, K ≤ 1000 будут получать не менее 50% баллов.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement