(cache)Submission #66871172 - AtCoder Beginner Contest 408

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

Submission #66871172

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>
#include <stdlib.h>
struct edge_s {
  int to, w;
};
int ec[212345];
struct edge_s* es[212345];
void ae(int f, int t, int w) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = (struct edge_s){ t, w };
}
int visited[212345];
/* mask が 1 → このビットは 1 であってもよい */
int dfs(int cur, int goal, int gen, int mask) {
  int i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct edge_s {
	int to, w;
};

int ec[212345];
struct edge_s* es[212345];

void ae(int f, int t, int w) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = (struct edge_s){ t, w };
}

int visited[212345];

/* mask が 1 → このビットは 1 であってもよい */
int dfs(int cur, int goal, int gen, int mask) {
	int i;
	if (visited[cur] == gen) return 0;
	visited[cur] = gen;
	if (cur == goal) return 1;
	for (i = 0; i < ec[cur]; i++) {
		if ((es[cur][i].w & ~mask) == 0) {
			if (dfs(es[cur][i].to, goal, gen, mask)) return 1;
		}
	}
	return 0;
}

int main(void) {
	int N, M;
	int i;
	int ans = 0;
	int gen = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int u, v, w;
		if (scanf("%d%d%d", &u, &v, &w) != 3) return 1;
		ae(u, v, w);
		ae(v, u, w);
	}
	for (;;) {
		/* 「全ビット1でよい」が一番条件が緩い、「全ビット1ではダメ」が一番条件がきつい */
		int yes = 31, no = -1;
		while (no + 1 < yes) {
			int m = no + (yes - no) / 2;
			if (dfs(1, N, ++gen, ans | ((1 << m) - 1))) yes = m; else no = m;
		}
		if (no == -1) break;
		/* 「このビットが1だとダメ」な最上位ビットを1にすることを許可する */
		ans |= 1 << no;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time	2025-06-19 01:20:07
Task	E - Minimum OR Path
User	mikecat
Language	C (gcc 12.2.0)
Score	450
Code Size	1408 Byte
Status	AC
Exec Time	2443 ms
Memory	26736 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 3

× 35

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All	00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	1 ms	1636 KiB
00_sample_01.txt	AC	1 ms	1624 KiB
00_sample_02.txt	AC	0 ms	1720 KiB
01_handmade_00.txt	AC	1 ms	1640 KiB
01_handmade_01.txt	AC	0 ms	1720 KiB
01_handmade_02.txt	AC	38 ms	5124 KiB
01_handmade_03.txt	AC	35 ms	5144 KiB
01_handmade_04.txt	AC	0 ms	1624 KiB
01_handmade_05.txt	AC	1 ms	1648 KiB
01_handmade_06.txt	AC	1 ms	1632 KiB
01_handmade_07.txt	AC	60 ms	9220 KiB
01_handmade_08.txt	AC	61 ms	9064 KiB
01_handmade_09.txt	AC	60 ms	9088 KiB
02_random_00.txt	AC	97 ms	7948 KiB
02_random_01.txt	AC	220 ms	6528 KiB
02_random_02.txt	AC	42 ms	4040 KiB
02_random_03.txt	AC	284 ms	8348 KiB
02_random_04.txt	AC	158 ms	8136 KiB
02_random_05.txt	AC	281 ms	9680 KiB
02_random_06.txt	AC	165 ms	6488 KiB
02_random_07.txt	AC	526 ms	9360 KiB
02_random_08.txt	AC	794 ms	13868 KiB
02_random_09.txt	AC	308 ms	9188 KiB
02_random_10.txt	AC	258 ms	9780 KiB
02_random_11.txt	AC	149 ms	11208 KiB
02_random_12.txt	AC	211 ms	8568 KiB
02_random_13.txt	AC	343 ms	14040 KiB
02_random_14.txt	AC	179 ms	13008 KiB
02_random_15.txt	AC	66 ms	5388 KiB
02_random_16.txt	AC	1167 ms	16856 KiB
02_random_17.txt	AC	112 ms	16880 KiB
02_random_18.txt	AC	623 ms	16724 KiB
02_random_19.txt	AC	2443 ms	26612 KiB
02_random_20.txt	AC	234 ms	26736 KiB
02_random_21.txt	AC	1753 ms	26704 KiB