(cache)Submission #75933522 - AtCoder Beginner Contest 448

Contest Duration: 2026-03-07(Sat) 21:00 - 2026-03-07(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #75933522

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int ec[212345], *es[212345];
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;
}
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int zac;
int zal[212345];
int zaq(int q) {
  int l = 0, r = zac - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (zal[m] == q) return m;
    else if (zal[m] < q) l = m + 1;
    else r = m - 1;
  }
  printf("ERROR: %d not found!\n", q);
  exit(72);
}
int N;
int A[212345];
int cnt[212345];
char is_yes[212345];
void meow(int node, int parent, int kakutei) {
  int i;
  int id = zaq(A[node]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

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

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;
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int zac;
int zal[212345];

int zaq(int q) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == q) return m;
		else if (zal[m] < q) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found!\n", q);
	exit(72);
}

int N;
int A[212345];

int cnt[212345];
char is_yes[212345];

void meow(int node, int parent, int kakutei) {
	int i;
	int id = zaq(A[node]);
	is_yes[node] = kakutei || cnt[id] > 0;
	cnt[id]++;
	for (i = 0; i < ec[node]; i++) {
		int next = es[node][i];
		if (next != parent) meow(next, node, is_yes[node]);
	}
	cnt[id]--;
}

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 1; i < N; i++) {
		int U, V;
		if (scanf("%d%d", &U, &V) != 2) return 1;
		ae(U, V);
		ae(V, U);
	}
	memcpy(zal, A + 1, sizeof(*A) * N);
	qsort(zal, N, sizeof(*zal), cmp);
	for (zac = 1, i = 1; i < N; i++) {
		if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
	}
	meow(1, 0, 0);
	for (i = 1; i <= N; i++) {
		puts(is_yes[i] ? "Yes" : "No");
	}
	return 0;
}

Submission Info

Submission Time	2026-05-18 20:42:15
Task	D - Integer-duplicated Path
User	mikecat
Language	C23 (GCC 14.2.0)
Score	400
Code Size	1485 Byte
Status	AC
Exec Time	117 ms
Memory	25400 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 47

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt, sample_03.txt
All	hack_01.txt, hack_02.txt, hack_03.txt, hack_04.txt, hack_05.txt, hack_06.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt

Case Name	Status	Exec Time	Memory
hack_01.txt	AC	107 ms	19164 KiB
hack_02.txt	AC	103 ms	19172 KiB
hack_03.txt	AC	45 ms	13240 KiB
hack_04.txt	AC	43 ms	12904 KiB
hack_05.txt	AC	83 ms	18896 KiB
hack_06.txt	AC	84 ms	18860 KiB
sample_01.txt	AC	0 ms	1684 KiB
sample_02.txt	AC	0 ms	1628 KiB
sample_03.txt	AC	0 ms	1808 KiB
test_01.txt	AC	0 ms	1812 KiB
test_02.txt	AC	0 ms	1628 KiB
test_03.txt	AC	117 ms	25400 KiB
test_04.txt	AC	116 ms	25372 KiB
test_05.txt	AC	115 ms	25320 KiB
test_06.txt	AC	112 ms	24936 KiB
test_07.txt	AC	79 ms	24576 KiB
test_08.txt	AC	70 ms	24580 KiB
test_09.txt	AC	87 ms	13648 KiB
test_10.txt	AC	90 ms	13652 KiB
test_11.txt	AC	85 ms	13616 KiB
test_12.txt	AC	81 ms	13216 KiB
test_13.txt	AC	54 ms	13292 KiB
test_14.txt	AC	43 ms	12856 KiB
test_15.txt	AC	104 ms	12848 KiB
test_16.txt	AC	104 ms	12848 KiB
test_17.txt	AC	104 ms	12784 KiB
test_18.txt	AC	103 ms	12616 KiB
test_19.txt	AC	65 ms	12328 KiB
test_20.txt	AC	58 ms	12120 KiB
test_21.txt	AC	95 ms	13200 KiB
test_22.txt	AC	96 ms	13296 KiB
test_23.txt	AC	93 ms	14184 KiB
test_24.txt	AC	87 ms	13352 KiB
test_25.txt	AC	54 ms	12088 KiB
test_26.txt	AC	54 ms	14216 KiB
test_27.txt	AC	114 ms	22116 KiB
test_28.txt	AC	110 ms	16680 KiB
test_29.txt	AC	113 ms	21872 KiB
test_30.txt	AC	110 ms	21200 KiB
test_31.txt	AC	67 ms	18736 KiB
test_32.txt	AC	68 ms	20388 KiB
test_33.txt	AC	110 ms	17668 KiB
test_34.txt	AC	114 ms	22224 KiB
test_35.txt	AC	112 ms	19816 KiB
test_36.txt	AC	103 ms	13732 KiB
test_37.txt	AC	79 ms	22692 KiB
test_38.txt	AC	64 ms	14776 KiB