babayka76

13.02.2023 16:50

Информатика

Есть ответ 👍

Задача C. Кибер-взлом Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мегабайт
Ви пытается взломать сервера корпорации Арасака, чтобы отключить охрану и проникнуть в
их офис. Искусственный интеллект сервера пытается ему в этом помешать.
Взлом происходит следующим образом. Рассмотрим ориентированный граф, на каждом ребре
которого написана буква английского алфавита. Граф может содержать кратные ребра и даже
петли. У Ви есть токен, изначально находящийся в некоторой вершине v, и у ИИ сервера есть
токен, изначально находящийся в некоторой вершине u. Затем они по-очереди совершают ходы, Ви
ходит первым. На своём ходу Ви выбирает произвольное ребро, исходящее из вершины, в которой
находится его токен. Он перемещает токен по этому ребру, а также пытается произвести атаку типа
c, где c — символ, написанный на выбранном ребре. ИИ на своём ходу также выбирает одно из
рёбер, исходящих из вершины, в которой находится его токен, и перемещает токен по этому ребру.
При этом, чтобы успешно отразить атаку, он должен выбрать ребро, на котором написан тот же
символ c.
Если Ви не может сделать ход, потому что из вершины, в которой находится его токен, не исходит
ни одного ребра, взлом завершается провалом. Если ИИ не может выбрать ребро, исходящее из
вершины, в которой находится его токен, на котором написан символ c, взлом завершается успешно.
Также, возможна ситуация, в которой Ви и ИИ будут делать ходы бесконечно долго.
Ви определить количество стартовых состояний, то есть пар вершин v и u, при которых
взлом будет произведен успешно при оптимальных действиях Ви и ИИ.
Формат входных данных
В первой строке даны два целых числа n и m — количество вершин и ребер в графе (1 6 n 6 1 000,
0 6 m 6 1 000).
В следующих m строках дано описание ребер графа. Каждая строка содержит два целых числа
ai и bi и строчную букву английского алфавита ci
, они обозначают ребро из вершины ai в вершину
bi
, на котором написан символ ci (1 6 ai
, bi 6 n).
Формат выходных данных
Выведите одно число — искомое количество стартовых состояний.
Система оценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Подзадача Ограничения Необходимые
подзадачи
Информация
о проверке
1 12 n, m 6 10 первая ошибка
2 21 n, m 6 100 1 первая ошибка
3 22 ci = ‘a’ первая ошибка
4 22 Граф является ациклическим первая ошибка
5 23 Без дополнительных ограничений 1–4 первая ошибка
Примеры
стандартный ввод стандартный вывод
3 3
1 2 a
2 3 b
3 1 c
6
5 10
2 2 c
3 5 b
5 4 b
2 3 b
3 5 c
3 1 b
4 2 a
4 4 a
2 4 b
2 5 c
15
Замечание
В первом примере, если изначально токены Ви и ИИ стоят в одной и той же вершине, процесс
никогда не завершится. Во всех остальных случаях, взлом будет успешным.