(cache)Submission #66754080 - AtCoder Beginner Contest 410

Contest Duration: 2025-06-14(Sat) 21:00 - 2025-06-14(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #66754080

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,M = map(int,input().split())
adj = [[] for i in range(N)]
for i in range(M):
    A, B, W = map(int,input().split())
    adj[A-1].append([B-1, W])
visited = [False for i in range(N)]
d = [0 for i in range(N)]
kitei = [0 for i in range(10)]
def add_kitei(x):
    for i in range(9, -1, -1):
        if not (x >> i) & 1:
            continue
        if kitei[i]:
            x ^= kitei[i]
        else:
            kitei[i] = x
            return
def dfs(u):
    visited[u] = True
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

N,M = map(int,input().split())
adj = [[] for i in range(N)]
for i in range(M):
    A, B, W = map(int,input().split())
    adj[A-1].append([B-1, W])

visited = [False for i in range(N)]
d = [0 for i in range(N)]
kitei = [0 for i in range(10)]

def add_kitei(x):
    for i in range(9, -1, -1):
        if not (x >> i) & 1:
            continue
        if kitei[i]:
            x ^= kitei[i]
        else:
            kitei[i] = x
            return
def dfs(u):
    visited[u] = True
    for v, w in adj[u]:
        if not visited[v]:
            d[v] = d[u] ^ w
            dfs(v)
        else:
            if d[u] ^ w ^ d[v]:
                add_kitei(d[u] ^ w ^ d[v])
dfs(0)
if not visited[N-1]:
    print(-1)
else:
    ans = d[N-1]
    for i in range(9, -1, -1):
        if kitei[i] and (ans ^ kitei[i]) < ans:
            ans ^= kitei[i]
    print(ans)

Submission Info

Submission Time	2025-06-14 21:43:53
Task	D - XOR Shortest Walk
User	hisi
Language	Python (PyPy 3.10-v7.3.12)
Score	0
Code Size	890 Byte
Status	WA
Exec Time	75 ms
Memory	81644 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

0 / 400

Status

× 3

AC	× 30
WA	× 3

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	64 ms	76836 KiB
hand_02.txt	AC	65 ms	76780 KiB
hand_03.txt	AC	66 ms	76576 KiB
hand_04.txt	AC	65 ms	76532 KiB
hand_05.txt	AC	64 ms	76452 KiB
hand_06.txt	WA	65 ms	76560 KiB
hand_07.txt	WA	64 ms	76668 KiB
hand_08.txt	WA	63 ms	76728 KiB
random_01.txt	AC	64 ms	76424 KiB
random_02.txt	AC	68 ms	76980 KiB
random_03.txt	AC	63 ms	76700 KiB
random_04.txt	AC	68 ms	76756 KiB
random_05.txt	AC	65 ms	76672 KiB
random_06.txt	AC	65 ms	76648 KiB
random_07.txt	AC	63 ms	76536 KiB
random_08.txt	AC	69 ms	76948 KiB
random_09.txt	AC	64 ms	76428 KiB
random_10.txt	AC	72 ms	81216 KiB
random_11.txt	AC	62 ms	76680 KiB
random_12.txt	AC	70 ms	76864 KiB
random_13.txt	AC	69 ms	81172 KiB
random_14.txt	AC	70 ms	80796 KiB
random_15.txt	AC	68 ms	80840 KiB
random_16.txt	AC	63 ms	76588 KiB
random_17.txt	AC	72 ms	81644 KiB
random_18.txt	AC	72 ms	81344 KiB
random_19.txt	AC	73 ms	81276 KiB
random_20.txt	AC	75 ms	81564 KiB
random_21.txt	AC	73 ms	80756 KiB
random_22.txt	AC	74 ms	80976 KiB
sample_01.txt	AC	63 ms	76664 KiB
sample_02.txt	AC	62 ms	76504 KiB
sample_03.txt	AC	64 ms	76544 KiB