Сделать задачи с codeforses
0
127
Тема: Обходы графов
A. Слияние множеств
ограничение по времени на тест
2 секундыограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.
Вам нужно выполнить M запросов. В каждом запросе даются целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если они уже в одном множестве, то ничего не делать).
Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).
В следующих M строках записаны по два целых числа – номера объектов, множества которых нужно объединить.
Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.
Пример
входные данные
В примере останутся два множества – {1, 2, 3, 4} и {5, 6}.
B. Объединения с отменами
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.
Вам нужно выполнить M запросов двух типов.
Первый тип запроса – объединение двух множеств. Вам даются два целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если объекты уже в одном множестве, то ничего делать не нужно).
Второй тип запроса – отмена последнего выполненного запроса на объединение. Учитываются и те запросы, в которых реального объединения не происходило (при отмене таких запросов также делать ничего не надо).
Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).
В каждой из следующих M строк записаны по два целых числа u и v. Если u > 0, v > 0, то это запрос первого типа, и вам нужно выполнить объединение множеств, содержащих эти элементы. Если же u = v = 0, то это запрос второго типа, и нужно выполнить отмену последнего выполненного запроса на объединение.
Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.
Примеры
входные данныеСкопировать
В первом примере останутся три множества – {1,2,3,5}, {4} и {6}.
Во втором примере останутся два множества – {1,2} и {3}.
C. Михаил Густокашин против бюрократии
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводЗадача классическая. Формулировка: Михаил Густокашин.
Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.
Всё было бы хорошо, но вот некоторые врачи отказываются ставить подписи на справке до тех пор, пока на ней не распишется другой врач. Например, стоматолог отказался ставить мне подпись, пока я не принесу справку от психиатра, потому, что однажды его укусил один психически неуравновешенный мальчик, да так, что бедному врачу пришлось два месяца сидеть на больничном. Теперь он у всех своих пациентов требует справку об отсутствии психических расстройств. Много странностей у врачей...
Закончилось тем, что я составил список, какому врачу нужны какие справки.
Входные данные
В первой строке моего списка содержится общее количество врачей (1 ≤ K ≤ 100). В следующих K строках описываются необходимые справки. Первое число (j) в i + 1 строке входных данных означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел – номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.
Выходные данные
Если подписи всех врачей собрать невозможно, то следует вывести "NO". Если же все справки собрать возможно, то в первой строке должно содержаться "YES", а в следующих K строках – последовательность, в которой нужно получать справки.
Пример
входные данные
Тема: Кратчайшие пути в графах
C. Цикл
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводДан взвешенный ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.
Входные данные
В первой строке входных данных записано число N (1 ≤ N ≤ 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.
Выходные данные
Выведите "YES", если цикл существует, и "NO" в противном случае.
Пример
входные данные
D. Автобусы
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводМежду некоторыми деревнями Пермской области ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день (например, в Ляды из Перми автобус приходит лишь 3 раза в сутки).
Ирине Владимировне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Входные данные
Во входных данных записано число N – общее число деревень (1 ≤ N ≤ 100), затем деревни d и v, затем количество автобусных рейсов R (0 ≤ R ≤ 10000).
Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000).
Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.
Выходные данные
Выведите минимальное время, когда пассажир может оказаться в деревне v. Если он не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.
Пример
входные данные
A. Слияние множеств
ограничение по времени на тест
2 секундыограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.
Вам нужно выполнить M запросов. В каждом запросе даются целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если они уже в одном множестве, то ничего не делать).
Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).
В следующих M строках записаны по два целых числа – номера объектов, множества которых нужно объединить.
Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.
Пример
входные данные
6 5 1 2 3 4 6 5 2 3 3 1выходные данные
2Примечание
В примере останутся два множества – {1, 2, 3, 4} и {5, 6}.
B. Объединения с отменами
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводИмеется N объектов, пронумерованных от 1 до N. Изначально каждый объект находится в своём собственном множестве, состоящем из одного элемента.
Вам нужно выполнить M запросов двух типов.
Первый тип запроса – объединение двух множеств. Вам даются два целых числа u и v – номера некоторых объектов. Требуется объединить множества, в которых лежат объекты u и v, в единое множество (а если объекты уже в одном множестве, то ничего делать не нужно).
Второй тип запроса – отмена последнего выполненного запроса на объединение. Учитываются и те запросы, в которых реального объединения не происходило (при отмене таких запросов также делать ничего не надо).
Входные данные
В первой строке входных данных записаны числа N и M (1 ≤ N ≤ 2·105, 0 ≤ M ≤ 2·105).
В каждой из следующих M строк записаны по два целых числа u и v. Если u > 0, v > 0, то это запрос первого типа, и вам нужно выполнить объединение множеств, содержащих эти элементы. Если же u = v = 0, то это запрос второго типа, и нужно выполнить отмену последнего выполненного запроса на объединение.
Выходные данные
Выведите одно число – количество множеств, оставшихся после выполнения всех запросов.
Примеры
входные данныеСкопировать
6 7 1 2 3 4 2 3 0 0 0 0 3 5 1 3выходные данные
3входные данные
3 5 1 2 2 3 3 1 0 0 0 0выходные данные
2Примечание
В первом примере останутся три множества – {1,2,3,5}, {4} и {6}.
Во втором примере останутся два множества – {1,2} и {3}.
C. Михаил Густокашин против бюрократии
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводЗадача классическая. Формулировка: Михаил Густокашин.
Как я уже писал, с 1 сентября 2002 года я буду учиться в СУНЦ МГУ (школа-интернат им А.Н. Колмогорова, ФМШ 18). Для того, чтобы я был допущен к занятиям, мне необходимо предъявить справку по форме 086/У, на которой должна поставить свои подписи K врачей.
Всё было бы хорошо, но вот некоторые врачи отказываются ставить подписи на справке до тех пор, пока на ней не распишется другой врач. Например, стоматолог отказался ставить мне подпись, пока я не принесу справку от психиатра, потому, что однажды его укусил один психически неуравновешенный мальчик, да так, что бедному врачу пришлось два месяца сидеть на больничном. Теперь он у всех своих пациентов требует справку об отсутствии психических расстройств. Много странностей у врачей...
Закончилось тем, что я составил список, какому врачу нужны какие справки.
Входные данные
В первой строке моего списка содержится общее количество врачей (1 ≤ K ≤ 100). В следующих K строках описываются необходимые справки. Первое число (j) в i + 1 строке входных данных означает, сколько справок нужно i-му врачу. Затем, в той же строке, содержится j чисел – номера врачей, чьи подписи надо предварительно поставить, чтобы получить подпись i-го врача.
Выходные данные
Если подписи всех врачей собрать невозможно, то следует вывести "NO". Если же все справки собрать возможно, то в первой строке должно содержаться "YES", а в следующих K строках – последовательность, в которой нужно получать справки.
Пример
входные данные
4выходные данные
1 2
0
2 1 4
1 1
YES
2
1
4
3
Тема: Кратчайшие пути в графах
C. Цикл
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводДан взвешенный ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.
Входные данные
В первой строке входных данных записано число N (1 ≤ N ≤ 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.
Выходные данные
Выведите "YES", если цикл существует, и "NO" в противном случае.
Пример
входные данные
2выходные данные
0 -1
-1 0
YES
D. Автобусы
ограничение по времени на тест
1 секундаограничение по памяти на тест
256 мегабайтввод
стандартный вводвывод
стандартный выводМежду некоторыми деревнями Пермской области ходят автобусы. Поскольку пассажиропотоки здесь не очень большие, то автобусы ходят всего несколько раз в день (например, в Ляды из Перми автобус приходит лишь 3 раза в сутки).
Ирине Владимировне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).
Входные данные
Во входных данных записано число N – общее число деревень (1 ≤ N ≤ 100), затем деревни d и v, затем количество автобусных рейсов R (0 ≤ R ≤ 10000).
Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000).
Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.
Выходные данные
Выведите минимальное время, когда пассажир может оказаться в деревне v. Если он не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.
Пример
входные данные
3выходные данные
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
5