Submission #66744598


Source Code Expand

Copy
T = 1
def init():
global T
#T = _I()
def ib(bs, x):
for b in bs:
x = min(x,x^b)
if x:
bs.append(x)
return bs
def minx(bs,x):
for b in sorted(bs,reverse=True):
x = min(x,x^b)
return x
def solve():
N,M = _M()
g = dd(list)
for i in range(M):
a,b,w = _M()
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
T = 1
def init():
    global T
    #T = _I()
def ib(bs, x):
    for b in bs:
        x = min(x,x^b)
    if x:
        bs.append(x)
    return bs

def minx(bs,x):
    for b in sorted(bs,reverse=True):
        x = min(x,x^b)
    return x
def solve():
    N,M = _M()
    g = dd(list)

    for i in range(M):
        a,b,w = _M()
        g[a].append((b, w))
        g[b].append((a, w))

    t = [-1]*(N+1)
    t[1] = 0
    b = []
    vis = [False]*(N+1)

    def dfs(u):
        vis[u] = True
        for v,w in g[u]:
            if t[v] == -1:
                t[v] = t[u]^w
                dfs(v)
            else:
                if vis[v]:
                    ib(b,t[u] ^w^ t[v]) #かわいいからスペース
    dfs(1)
    if t[N] == -1:
        print(-1)
    else:
        print(minx(b,t[N]))

#--------------ごっつりしていってね--------------
#あぁそうそう ごちうさ楽しみ

import sys
import math
from copy import deepcopy as dc
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict as dd
import heapq
from itertools import permutations as per
_S = input;_R = range;_P = print; _E = enumerate;
def _RR(a): return range(a-1,-1,-1)
def _I(): return int(_S())
def _M(): return map(int, _S().split())
def _SS(): return _S().strip().split()
def _L(): return list(_M())
def _LS(): return list(_S())
def _T(): return tuple(_M())
def yn(b): print("Yes" if b else "No")
def fs(b): print("First" if b else "Second")
def lis(c,*a):
    if not len(a): return 0 if c == 0 else []
    if c == 0: return a[0]
    return [lis(c-1,*a[1:]) for i in _R(a[0])]
def in2(a,fn):
    for i in _R(len(a)): a[i]=fn()
biga = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";smaa = "abcdefghijklmnopqrstuvwxyz"
ctoi = lambda c: ord(c) - ord('a')
ctoi2 = lambda c: ord(c) - ord('A')
itoc = lambda i: chr(ord('a') + i)
itoc2 = lambda i: chr(ord('A') + i)
inf = 10 ** 18
mod = 998244353
def around(x,y,type_=False):
    rt = []
    rt.extend([(x+1,y),(x-1,y),(x,y+1),(x,y-1)])
    if type_:
        rt.extend([(x+1,y+1),(x-1,y-1),(x-1,y+1),(x+1,y-1)])
    return rt
def acc(a):
    b = [0]
    for i in a:
        b.append(b[-1] + i)
    return b
class heap:
    l = []
    def __init__(self,*s): self.l = list(s);heapq.heapify(self.l)
    def min(self): return False if (len(self.l) == 0) else self.l[0]
    def pop(self): return False if (len(self.l) == 0) else heapq.heappop(self.l)
    def push(self,n): heapq.heappush(self.l,n)
    def dump(self): return heapq.nsmallest(len(self.l),self.l)
    def max(self): return False if (len(self.l) == 0) else heapq.nlargest(1,self.l)[0]
    def len(self): return len(self.l)
class base:
    bn = 0; dig = 0; num = []
    def __init__(self,base_num,digit = 0):
        self.bn = base_num; self.dig = digit; self.num = [0]*digit
    def max(self): return(self.bn**self.dig-1)
    def dump(self): return(self.num[::-1])
    def ncp(self,digit,n): self.num[digit] = min(self.num[digit]+n,self.bn-1)
    def plus(self,digit,n):
        for i in _R(digit-self.dig+1): self.num.append(0)
        self.dig = max(self.dig,digit+1)
        if (self.num[digit]+n >= self.bn):
            self.plus(digit+1,(self.num[digit]+n)//self.bn)
        self.num[digit] = (self.num[digit]+n)%self.bn
    def copy(self,n):
        self.num = dc(n)
        dig = len(self.num)
    def change(self,n):
        digit = int(math.log(n,self.bn))if n!=0 else 0+1
        for i in _R(digit-self.dig+1): self.num.append(0)
        self.dig = max(self.dig,digit+1)
        for i in _R(self.dig):
            self.num[i] = n%self.bn**(i+1)//self.bn**i
            n -= self.num[i]
        return self.dump()
    def b10(self): return(sum([self.num[i]*self.bn**i for i in _R(self.dig)]))
def gin(N, M=None):
    g = [[] for _ in range(N)]
    for _ in range(N-1 if M is None else M):
        u, v = map(int, input().split());u -= 1;v -= 1
        g[u].append(v);g[v].append(u)
    return g
def ginh(N, M):
    g = [[] for _ in range(N)]
    for i in range(M):
        u, v, h = map(int, input().split());u -= 1;v -= 1
        g[u].append((v,h));g[v].append((u,h))
    return g
from atcoder.segtree import SegTree
class rhash:
    hs = None
    def __init__(self,S,N):
        self.hs = SegTree(msum,0,[ctoi(S[i])*pow(31,i,mod) for i in _R(N)])
    def get(self,l,r):
        return self.hs.prod(l,r+1)*pow(pow(31,l,mod),mod-2,mod)%mod
    def getall(self):
        return self.hs.all_prod()
    def change(self,n,c):
        self.hs.set(n,ctoi(c)*pow(31,n,mod))
def nwse(s,x,y,rev=False):
    if (rev):
        s = {"N":"S","S":"N","W":"E","E":"W"}[s]
    if s=="N": return (x-1,y)
    elif s=="W": return (x,y-1)
    elif s=="S": return (x+1,y)
    elif s=="E": return (x,y+1)

init()
for i in _R(T):
    solve()

Submission Info

Submission Time
Task D - XOR Shortest Walk
User potat_p
Language Python (PyPy 3.10-v7.3.12)
Score 0
Code Size 4874 Byte
Status WA
Exec Time 152 ms
Memory 87016 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 28
WA × 5
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 134 ms 84248 KiB
hand_02.txt AC 134 ms 84336 KiB
hand_03.txt WA 134 ms 84364 KiB
hand_04.txt AC 134 ms 84312 KiB
hand_05.txt WA 135 ms 84484 KiB
hand_06.txt WA 135 ms 84384 KiB
hand_07.txt WA 135 ms 84208 KiB
hand_08.txt WA 138 ms 84380 KiB
random_01.txt AC 136 ms 84236 KiB
random_02.txt AC 140 ms 85264 KiB
random_03.txt AC 134 ms 84288 KiB
random_04.txt AC 137 ms 84624 KiB
random_05.txt AC 134 ms 84464 KiB
random_06.txt AC 136 ms 84516 KiB
random_07.txt AC 134 ms 84376 KiB
random_08.txt AC 140 ms 84848 KiB
random_09.txt AC 133 ms 84344 KiB
random_10.txt AC 148 ms 86592 KiB
random_11.txt AC 134 ms 84328 KiB
random_12.txt AC 140 ms 84996 KiB
random_13.txt AC 140 ms 84812 KiB
random_14.txt AC 142 ms 84808 KiB
random_15.txt AC 140 ms 84592 KiB
random_16.txt AC 136 ms 84408 KiB
random_17.txt AC 149 ms 86052 KiB
random_18.txt AC 148 ms 86644 KiB
random_19.txt AC 150 ms 87016 KiB
random_20.txt AC 149 ms 86536 KiB
random_21.txt AC 152 ms 85836 KiB
random_22.txt AC 150 ms 85784 KiB
sample_01.txt AC 134 ms 84572 KiB
sample_02.txt AC 135 ms 84320 KiB
sample_03.txt AC 135 ms 84396 KiB


2025-08-22 (Fri)
01:26:30 +09:00