(cache)Submission #73868025 - AtCoder Beginner Contest 435

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

Submission #73868025

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>
int ec[312345], *es[312345];
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
}
char visited[312345];
void mark(int node) {
  int i;
  if (visited[node]) return;
  visited[node] = 1;
  for (i = 0; i < ec[node]; i++) {
    mark(es[node][i]);
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int ec[312345], *es[312345];

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

char visited[312345];

void mark(int node) {
	int i;
	if (visited[node]) return;
	visited[node] = 1;
	for (i = 0; i < ec[node]; i++) {
		mark(es[node][i]);
	}
}

int main(void) {
	int N, M, Q;
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int X, Y;
		if (scanf("%d%d", &X, &Y) != 2) return 1;
		ae(Y, X);
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		int type, v;
		if (scanf("%d%d", &type, &v) != 2) return 1;
		switch (type) {
			case 1:
				mark(v);
				break;
			case 2:
				puts(visited[v] ? "Yes" : "No");
				break;
		}
	}
	return 0;
}

/*

辺を逆向きにしておく
頂点を黒色にする → そこから(逆向きの辺で)到達可能な頂点に到達可能フラグを立てる
既に到達可能フラグが立っていたら、打ち切る

*/

Submission Info

Submission Time	2026-03-07 02:48:11
Task	D - Reachability Query 2
User	mikecat
Language	C23 (GCC 14.2.0)
Score	425
Code Size	1079 Byte
Status	AC
Exec Time	117 ms
Memory	28912 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

425 / 425

Status

× 1

× 30

Set Name	Test Cases
Sample	sample_01.txt
All	min.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, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, sample_01.txt

Case Name	Status	Exec Time	Memory
min.txt	AC	0 ms	1692 KiB
random_01.txt	AC	84 ms	11224 KiB
random_02.txt	AC	84 ms	11436 KiB
random_03.txt	AC	53 ms	5660 KiB
random_04.txt	AC	69 ms	6836 KiB
random_05.txt	AC	30 ms	1968 KiB
random_06.txt	AC	25 ms	1632 KiB
random_07.txt	AC	40 ms	2780 KiB
random_08.txt	AC	90 ms	10448 KiB
random_09.txt	AC	41 ms	2860 KiB
random_10.txt	AC	44 ms	3056 KiB
random_11.txt	AC	64 ms	5696 KiB
random_12.txt	AC	93 ms	10924 KiB
random_13.txt	AC	41 ms	2780 KiB
random_14.txt	AC	35 ms	2608 KiB
random_15.txt	AC	60 ms	7244 KiB
random_16.txt	AC	72 ms	7768 KiB
random_17.txt	AC	58 ms	3316 KiB
random_18.txt	AC	74 ms	14876 KiB
random_19.txt	AC	25 ms	1744 KiB
random_20.txt	AC	37 ms	2640 KiB
random_21.txt	AC	89 ms	10192 KiB
random_22.txt	AC	78 ms	14916 KiB
random_23.txt	AC	68 ms	6640 KiB
random_24.txt	AC	75 ms	14892 KiB
random_25.txt	AC	117 ms	28912 KiB
random_26.txt	AC	113 ms	26800 KiB
random_27.txt	AC	85 ms	14832 KiB
random_28.txt	AC	58 ms	3356 KiB
sample_01.txt	AC	1 ms	1588 KiB