| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 34 | 12 | 5 | 31.250% |
В условиях нехватки энергии Матрица была модифицирована, чтобы расходовать как можно меньше энергетических ресурсов. Всего есть $n$ узлов Матрицы с уникальными номерами от 1ドル$ до $n$. Изначально энергия есть только в генераторе, который является узлом с номером 1ドル$.
Требующие энергии узлы постепенно подключаются к уже запитанным узлам, и начинают получать энергию от них, образуя сеть питания в виде дерева. Некоторые узлы могут отказывать и восстанавливаться спустя время после отказа. Уже подключенный к сети узел никогда не переподключается к другим узлам, даже если какой-то из косвенно питающих его узлов отказал.
Ненадежностью узла называется время, прошедшее с момента его последнего восстановления (либо с момента подключения этого узла к сети, если он еще не отказывал). Временем подключения генератора считается момент времени 0ドル$.
Требуется обработать $m$ событий. Событие номер $i$ происходит ровно спустя $i$ секунд от начала и может быть одного из следующих видов:
! $x_i$ $y_i$>> --- узел $y_i$ подключается к узлу $x_i$ и начинает получать энергию от него;- $x_i$>> --- узел $x_i$ отказывает и перестает проводить энергию;+ $x_i$>> --- ранее отказавший узел $x_i$ восстанавливается и продолжает проводить энергию;? $x_i$ $y_i$>> --- требуется выяснить, насколько надежна пара узлов $x_i$ и $y_i$.Для ответа на запрос последнего типа требуется проверить, получают ли энергию оба узла $x_i$ и $y_i$. Узел получает энергию, если сам подключен к сети, и все узлы на пути от генератора до него включительно находятся в исправном состоянии (не отказали). Если оба узла $x_i$ и $y_i$ получают энергию, требуется вывести суммарную ненадежность всех узлов, от которых зависит работа хотя бы одного из узлов $x_i$ или $y_i$ (то есть узлов, расположенных на путях от них до генератора).
В первой строке ввода через пробел даны два целых числа $n$ и $m$ --- общее количество узлов, которым требуется питание, и количество событий, которые надо обработать (2ドル \leqslant n, m \leqslant 2 \cdot 10^5$).
В $i$-й из следующих $m$ строк дано описание $i$-го запроса (который происходит в момент времени $i$). Описание формата запросов дано в условии. За символом, обозначающим тип запроса, в зависимости от этого типа, следует либо одно целое число $x_i,ドル либо два целых числа $x_i$ и $y_i,ドル разделенные пробелом --- номера задействованных в запросе узлов (1ドル \leqslant x_i, y_i \leqslant n$; $x_i \neq y_i$).
Гарантируется, что в запросе первого типа узел $x_i$ уже подключен к сети, а $y_i$ --- нет. Также для запросов второго и третьего типа гарантируется, что узел $x_i$ отказывает только если был до этого исправен, и наоборот, восстанавливается только после соответствующего отказа.
После каждого запроса четвертого типа следует в отдельной строке вывести ответ на этот запрос. Если хотя бы один из узлов $x_i$ и $y_i$ не получает энергию, следует вывести <<-1>> (без кавычек). Если же оба узла получают энергию, следует вывести целое число, равное сумме ненадежностей всех узлов, лежащих на путях от генератора до $x_i$ и $y_i$.
3 7 ! 1 2 ! 1 3 ? 2 3 - 3 ? 2 3 + 3 ? 2 3
6 -1 14
3 7 ! 1 2 ! 2 3 ? 1 3 - 2 ? 1 3 + 2 ? 1 3
6 -1 13
В первом примере отказ третьего узла, очевидно, влечет ответ <<-1>> на второй запрос <<? 2 3>>. Ответ на первый запрос равен 6ドル,ドル так как с момента подключения к сети генератора, второго узла и третьего, прошли 3ドル,ドル 2ドル$ и 1ドル$ секунда, соответственно. В момент третьего запроса с момента подключения генератора и второго узла прошло 7ドル$ и 6ドル$ секунд, соответственно, тогда как третий узел вернулся в строй ровно 1ドル$ секунду назад, что дает ответ 14ドル$.
Во втором примере отказ второго узла аналогично влечет ответ <<-1>> на второй запрос. Ответ на первый запрос вычисляется так же, как и в первом примере, а на третий --- как 7ドル + 1 + 5 = 13$.