| Codeforces Global Round 6 |
|---|
| Закончено |
Дан ориентированный граф из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, в котором из каждой вершины (кроме $$$n$$$) исходит две дуги, красная и синяя. В любой момент времени ровно одна исходящая дуга является активной для каждой вершины. Изначально все синие дуги активны, а в вершине $$$1$$$ находится фишка. В начале каждой секунды у вершины, в которой стоит фишка, меняется активная дуга. Затем фишка перемещается по активной дуге. Когда фишка достигает вершины $$$n$$$, она останавливается. Гарантируется, что вершина $$$n$$$ достижима по дугам из всех остальных вершин графа.
Вам задаются $$$q$$$ запросов, в каждом из которых описывается состояние графа — пара $$$(v, s)$$$ следующего вида:
- $$$v$$$ — вершина, в которой находится фишка;
- $$$s$$$ — строка из $$$n - 1$$$ символов. $$$i$$$-й символ обозначает, какая дуга, ведущая из $$$i$$$, активна (красная, если символ равен 'R', или синяя, если символ — 'B').
Для каждого запроса определите, достижимо ли заданное состояние из стартового, и если да — когда такое состояние графа появится в первый раз. Обратите внимание, что заданные две операции неразрывны между собой — состояние не считается достигнутым, если оно появляется после изменения активной дуги, но до того, как фишку переместили по дуге.
В первой строке задано одно целое число $$$n$$$ ($$$2 \leq n \leq 58$$$) — количество вершин.
Далее следуют $$$n-1$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$b_i$$$ и $$$r_i$$$ ($$$1 \leq b_i, r_i \leq n$$$), обозначающих синюю дугу $$$(i, b_i)$$$ и красную дугу $$$(i, r_i)$$$, соответственно. Гарантируется, что вершина $$$n$$$ достижима из всех остальных.
Следующая строка содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 5000$$$) — количество запросов.
Затем следуют $$$q$$$ строк с запросами. $$$j$$$-я из них содержит целое число $$$v$$$ ($$$1 \leq v < n$$$) и строку $$$s$$$ из $$$n-1$$$ символов, каждый из которых либо 'R', либо 'B'. $$$i$$$-й из этих символов равен 'R', если красная дуга, ведущая из вершины $$$i$$$, активна, иначе этот символ равен 'B'.
Выведите $$$q$$$ чисел, каждое из которых содержит ответ на один запрос.
Если состояние в $$$i$$$-м запросе недостижимо, выведите $$$-1$$$. Иначе выведите $$$t_i$$$ — первый момент времени, когда это состояние появилось (выводите время в секундах, начиная отсчет с секунды $$$0$$$, в которую появилось стартовое состояние).
6 2 1 5 5 2 1 6 3 4 3 21 1 BBBBB 1 RBBBB 2 BBBBB 5 BRBBB 3 BRBBR 1 BRRBR 1 RRRBR 2 BRRBR 5 BBRBR 4 BBRBB 3 BBRRB 2 BBBRB 5 BRBRB 3 BRBRR 1 BRRRR 1 RRRRR 2 BRRRR 5 BBRRR 4 BBRRB 2 BRBBB 4 BRBBR
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 -1 -1
На картине изображен граф из первого примера.
Первые $$$19$$$ запросов показывают перемещение фишки. После $$$19$$$-го шага фишка достигает вершины $$$6$$$. Последние два запроса соответствуют недостижимым состояниям.
