Submission #66748218

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Original C++ Code:
# 
# #include <bits/stdc++.h>
# 
# using namespace std;
# 
# const int N = 1e5 + 1;
# 
# struct Basis{
#     vector<int>basis;
#     Basis(){
#     }
#     void insert(int x){
#         for (int i : basis) {
#             x = min(x, x ^ i);
#         }
#         if (x) basis.push_back(x);
#     }
#     int get(int x) {
#         for (int i : basis) {
#             x = min(x, x ^ i);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

# Original C++ Code:
# 
# #include <bits/stdc++.h>
# 
# using namespace std;
# 
# const int N = 1e5 + 1;
# 
# struct Basis{
#     vector<int>basis;
#     Basis(){
#     }
#     void insert(int x){
#         for (int i : basis) {
#             x = min(x, x ^ i);
#         }
#         if (x) basis.push_back(x);
#     }
#     int get(int x) {
#         for (int i : basis) {
#             x = min(x, x ^ i);
#         }
#         return x;
#     }
# };
# 
# vector<pair<int, int>> g[N];
# bool vis[N];
# int XOR[N];
# Basis b;
# 
# void dfs(int u, int p = -1, int d = 0) {
#     vis[u] = true;
#     XOR[u] = d;
#     for (auto [v, w]: g[u]) {
#         if (!vis[v]) {
#             dfs(v, u, w ^ d);
#         }
#         else if (v != p) {
#             b.insert(XOR[u] ^ XOR[v] ^ w);
#         }
#     }
# }
# 
# void do_work(){
#     int n, m;
#     cin >> n >> m;
#     for (int i = 0; i < m; i++) {
#         int u, v, w;
#         cin >> u >> v >> w;
#         u--; v--;
#         g[u].emplace_back(v, w);
#         g[v].emplace_back(u, w);
#     }
#     dfs(0);
#     cout << b.get(XOR[n - 1]) << '\n';
# }
# 
# int main(){
# #ifndef ONLINE_JUDGE
#     freopen("input.txt", "r", stdin);
#     freopen("output.txt", "w", stdout);
# #endif
#     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#     int T = 1;
#     for(int i = 1; i <= T; i++){
#         do_work();
#     }
# }

# Translated Python Code:

import sys
sys.setrecursionlimit(10**6)

N = 10**5 + 1

class Basis:
    def __init__(self):
        self.basis = []

    def insert(self, x):
        for i in self.basis:
            x = min(x, x ^ i)
        if x:
            self.basis.append(x)

    def get(self, x):
        for i in self.basis:
            x = min(x, x ^ i)
        return x

g = [[] for _ in range(N)]
vis = [False] * N
XOR = [0] * N
b = Basis()

def dfs(u, p=-1, d=0):
    vis[u] = True
    XOR[u] = d
    for vw in g[u]:
        v, w = vw
        if not vis[v]:
            dfs(v, u, w ^ d)
        elif v != p:
            b.insert(XOR[u] ^ XOR[v] ^ w)

def do_work():
    n, m = map(int, sys.stdin.readline().split())
    for _ in range(m):
        u, v, w = map(int, sys.stdin.readline().split())
        u -= 1
        v -= 1
        g[u].append((v, w))
    dfs(0)
    ans = b.get(XOR[n - 1])
    if not vis[n-1]:
      print(-1)
    else:
      print(ans)

if __name__ == "__main__":
    T = 1
    for _ in range(T):
        do_work()

Submission Info

Judge Result