(cache)Submission #67174036 - 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 #67174036

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
#include <stdio.h>
#define INF 1010101010
struct edge_s {
  int to, w;
};
int ec[1024];
struct edge_s es[1024][1024];
int N;
int memo[1024][1024];
int calc(int node, int omomi) {
  int ans = INF;
  int i;
  if (memo[node][omomi]) return ~memo[node][omomi];
  memo[node][omomi] = ~INF;
  if (node == N) ans = omomi;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define INF 1010101010

struct edge_s {
	int to, w;
};

int ec[1024];
struct edge_s es[1024][1024];

int N;

int memo[1024][1024];

int calc(int node, int omomi) {
	int ans = INF;
	int i;
	if (memo[node][omomi]) return ~memo[node][omomi];
	memo[node][omomi] = ~INF;
	if (node == N) ans = omomi;
	for (i = 0; i < ec[node]; i++) {
		int candidate = calc(es[node][i].to, omomi ^ es[node][i].w);
		if (candidate < ans) ans = candidate;
	}
	return ~(memo[node][omomi] = ~ans);
}

int main(void) {
	int M;
	int i;
	int ans;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int A, B, W;
		if (scanf("%d%d%d", &A, &B, &W) != 3) return 1;
		es[A][ec[A]++] = (struct edge_s){ B, W };
	}
	ans = calc(1, 0);
	printf("%d\n", ans < INF ? ans : -1);
	return 0;
}

Submission Info

Submission Time	2025-06-29 07:58:16
Task	D - XOR Shortest Walk
User	mikecat
Language	C (gcc 12.2.0)
Score	400
Code Size	833 Byte
Status	AC
Exec Time	39 ms
Memory	13652 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 33

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	1 ms	1632 KiB
hand_02.txt	AC	1 ms	1728 KiB
hand_03.txt	AC	1 ms	1624 KiB
hand_04.txt	AC	0 ms	1636 KiB
hand_05.txt	AC	1 ms	1780 KiB
hand_06.txt	AC	1 ms	1680 KiB
hand_07.txt	AC	1 ms	1648 KiB
hand_08.txt	AC	1 ms	1768 KiB
random_01.txt	AC	1 ms	1864 KiB
random_02.txt	AC	3 ms	6496 KiB
random_03.txt	AC	1 ms	1788 KiB
random_04.txt	AC	2 ms	4808 KiB
random_05.txt	AC	1 ms	1948 KiB
random_06.txt	AC	1 ms	3440 KiB
random_07.txt	AC	1 ms	1656 KiB
random_08.txt	AC	3 ms	5928 KiB
random_09.txt	AC	1 ms	2020 KiB
random_10.txt	AC	4 ms	8452 KiB
random_11.txt	AC	1 ms	1808 KiB
random_12.txt	AC	3 ms	6564 KiB
random_13.txt	AC	4 ms	4840 KiB
random_14.txt	AC	8 ms	9760 KiB
random_15.txt	AC	2 ms	2764 KiB
random_16.txt	AC	1 ms	2008 KiB
random_17.txt	AC	5 ms	9784 KiB
random_18.txt	AC	4 ms	9608 KiB
random_19.txt	AC	39 ms	9664 KiB
random_20.txt	AC	12 ms	5692 KiB
random_21.txt	AC	17 ms	13588 KiB
random_22.txt	AC	18 ms	13652 KiB
sample_01.txt	AC	1 ms	1732 KiB
sample_02.txt	AC	1 ms	1656 KiB
sample_03.txt	AC	1 ms	1660 KiB