| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Совсем недавно в Берляндии была построена новая дорожная сеть. Между некоторыми парами городов есть односторонние дороги, $i$-я из которых ведёт из города $u_i$ в город $v_i,ドル а её длина равна $w_i$. Два главных города Берляндии имеют номера $a$ и $b$.
Король Берляндии очень любит свою страну. В частности, он обожает подсчитывать всякие характеристики в ней. Он называет красотой пути побитовое исключающее ИЛИ длин всех дорог на этом пути. А красотой своей страны он называет побитовое исключающее ИЛИ красот всех путей из города $a$ в город $b$. Обратите внимание, что таких путей может быть бесконечно много, и они могут проходить через один и тот же город несколько раз.
Король хочет узнать, чему равна красота его страны, а поэтому он обратился к вам за помощью и просит вас посчитать это значение или сказать, что красоту страны посчитать невозможно.
Побитовым исключающим ИЛИ множества чисел называется побитовое исключающее ИЛИ всех ненулевых чисел в этом множестве. Если в множестве бесконечно много ненулевых чисел, то побитовое исключающее ИЛИ посчитать невозможно. \\
Побитовое исключающее ИЛИ (или побитовое сложение по модулю два) --- это бинарная операция, действие которой эквивалентно применению логического исключающего ИЛИ к каждой паре битов, которые стоят на одинаковых позициях в двоичной записи операндов. Иными словами, если соответствующие биты операндов различны, то соответствующий двоичный разряд результата равен 1; если же биты одинаковые, то двоичный разряд результата равен 0. Например, если $x = 109_{10} = 1101101_2,ドル а $y = 41_{10} = 101001_2,ドル то их побитовое исключающее ИЛИ равно $x \oplus y = 1000100_2 = 68_{10}$.
Путём в графе называется последовательность вершин, в которой любые две последовательные вершины соединены ребром.
Каждый тест состоит из нескольких наборов входных данных. В первой строке дано одно целое число $t$ (1ドル \le t \le 40,000円$) --- количество наборов входных данных.
В первой строке каждого набора входных данных даны два целых числа $n$ и $m$ (1ドル \le n, m \le 200,000円$) --- количество городов и количество дорог в Берляндии.
В следующих $m$ строках даны по три целых числа $u_i,ドル $v_i$ и $w_i$ (1ドル \le u_i, v_i \le n,ドル 0ドル \le w_i \le 2^{30}-1$) --- номера начала и конца $i$-й дороги и её длина.
Последняя строка каждого набора входных данных содержит два целых числа $a$ и $b$ (1ドル \le a, b \le n$) --- номера начала и конца путей, которые интересуют короля.
Обозначим за $\sum n$ сумму $n,ドル а за $\sum m$ сумму $m$ по всем наборам входных данных в одном тесте. Гарантируется, что $\sum n \le 200,000円$ и $\sum m \le 200,000円$.
Для каждого набора входных данных выведите одно целое число --- красоту Берляндии. Если ответа не существует, то выведите $-1$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 16 | $n = m,ドル $u_i = i, v_i = i + 1$ для $i < n,ドル $u_{n} = n, v_{n} = 1$ |
| 2 | 17 | $w_i \le 1,ドル $u_i < v_i$ |
| 3 | 15 | $u_i < v_i$ |
| 4 | 19 | $\sum n \le 1000,ドル $\sum m \le 1000,ドル $w_i \le 2^{10} - 1$ |
| 5 | 14 | $w_i \le 1$ |
| 6 | 19 |
5 1 1 1 1 0 1 1 3 5 1 2 0 1 2 1 1 2 3 2 3 5 2 3 2 1 3 2 2 1 2 1 2 1 2 1 2 3 3 1 2 7 2 3 0 3 1 7 2 3 4 5 1 1 0 1 2 3 2 2 0 2 3 1 3 4 1 1 4
0 7 -1 0 -1
В первом наборе входных данных в стране есть только одна дорога длины 0ドル,ドル поэтому красота любого пути равна 0ドル,ドル а тогда и побитовое исключающее ИЛИ красот всех путей равно 0ドル$.
Во втором наборе входных данных в стране есть всего 6ドル$ возможных путей из города 1ドル$ в город 3ドル,ドル красоты которых равны 0ドル \oplus 5 = 5, 0 \oplus 2 = 2, 1 \oplus 5 = 4, 1 \oplus 2 = 3, 3 \oplus 5 = 6, 3 \oplus 2 = 1$. Тогда красота страны равна 5ドル \oplus 2 \oplus 4 \oplus 3 \oplus 6 \oplus 1 = 7$.
В третьем наборе входных данных из города 1ドル$ в город 2ドル$ есть пути красоты 1,ドル 1 \oplus 2 \oplus 1 = 2, 1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 1, 1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 \oplus 2 \oplus 1 = 2, \ldots$. Тогда из города 1ドル$ в город 2ドル$ есть бесконечно много путей с ненулевой красотой, а значит ответ посчитать нельзя.
В четвёртом наборе входных данных из вершины 2ドル$ в вершину 3ドル$ есть бесконечно много путей красоты 0ドル,ドル и нет ни одного пути с ненулевой красотой. Тогда итоговая красота страны равна 0ドル$.
Olympiad > Moscow Open Olympiad in Informatics > Moscow Open Olympiad in Informatics 2022-23 > Day 1 Pac-Man번