Submission #66768771

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys, time, random, heapq, math, itertools
from collections import deque, Counter, defaultdict
from sortedcontainers import SortedSet, SortedList
from bisect import bisect, bisect_left, bisect_right
import heapq as hq
from functools import cache, cmp_to_key
def debug(*x):print('debug:',*x, file=sys.stderr)
sys.setrecursionlimit(300000)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 61 - 1
mod = 998244353
def dfs(n,cnt):
    global base,d
    d[n] = cnt 
    for k,w in g[n]:
        if d[k] != -1:
            temp = cnt ^ w ^ d[k]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import sys, time, random, heapq, math, itertools
from collections import deque, Counter, defaultdict
from sortedcontainers import SortedSet, SortedList
from bisect import bisect, bisect_left, bisect_right
import heapq as hq
from functools import cache, cmp_to_key
def debug(*x):print('debug:',*x, file=sys.stderr)
sys.setrecursionlimit(300000)
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 61 - 1
mod = 998244353

def dfs(n,cnt):
    global base,d
    d[n] = cnt 
    for k,w in g[n]:
        if d[k] != -1:
            temp = cnt ^ w ^ d[k]
            if temp > 0:
                for b in base:
                    temp = min(temp, temp^b)
                if temp > 0:
                    base.append(temp)
                    base.sort(reverse=True)
        else:
            dfs(k, cnt^w)
            
    
N,M = mi()
g = [[] for _ in range(N)]
for i in range(M):
    a,b,w = mi()
    a-=1; b-=1
    g[a].append([b,w])


d = [-1]*N
base = []
dfs(0,0)  
#print(d)
#print(base)
if d[N-1] == -1:
    print(-1)
    exit()
ans = d[N-1]
for b in base:
    ans = min(ans, ans ^ b)
print(ans)

Submission Info

Judge Result