(cache)Submission #69249577 - パ研合宿2022　第1日「Jikka」

Contest Duration: 2023-03-27(Mon) 15:00 - 2023-03-27(Mon) 17:30 (local time) (150 minutes)

Submission #69249577

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>
int N;
int P[212345];
int Q;
int X[212345], Y[212345];
int depth[212345];
int ue[212345][20];
int get_ue(int from, int distance) {
  int i;
  int cur = from;
  for (i = 0; i < 20; i++) {
    if ((distance >> i) & 1) cur = ue[cur][i];
  }
  return cur;
}
int main(void) {
  int i, j;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
int P[212345];
int Q;
int X[212345], Y[212345];

int depth[212345];
int ue[212345][20];

int get_ue(int from, int distance) {
	int i;
	int cur = from;
	for (i = 0; i < 20; i++) {
		if ((distance >> i) & 1) cur = ue[cur][i];
	}
	return cur;
}

int main(void) {
	int i, j;
	if (scanf("%d", &N) != 1) return 1;
	depth[1] = 0;
	ue[1][0] = 1;
	for (i = 2; i <= N; i++) {
		if (scanf("%d", &P[i]) != 1) return 1;
		depth[i] = depth[P[i]] + 1;
		ue[i][0] = P[i];
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
	}

	for (j = 1; j < 20; j++) {
		for (i = 1; i <= N; i++) {
			ue[i][j] = ue[ue[i][j - 1]][j - 1];
		}
	}

	for (i = 0; i < Q; i++) {
		int dx = depth[X[i]], dy = depth[Y[i]];
		int dd = dy - dx;
		if (dd < 2) {
			puts("f*ck");
		} else {
			printf("%d\n", get_ue(Y[i], dd - 1));
		}
	}

	return 0;
}

Submission Info

Submission Time	2025-09-13 07:02:29
Task	G - Ancestor Query
User	mikecat
Language	C (gcc 12.2.0)
Score	400
Code Size	955 Byte
Status	AC
Exec Time	240 ms
Memory	20504 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

400 / 400

Status

× 3

× 32

Set Name	Test Cases
Sample	example-01.txt, example-02.txt, example-03.txt
All	example-01.txt, example-02.txt, example-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

Case Name	Status	Exec Time	Memory
example-01.txt	AC	1 ms	1640 KiB
example-02.txt	AC	1 ms	1644 KiB
example-03.txt	AC	0 ms	1616 KiB
test-01.txt	AC	1 ms	1728 KiB
test-02.txt	AC	1 ms	1656 KiB
test-03.txt	AC	1 ms	1740 KiB
test-04.txt	AC	1 ms	1644 KiB
test-05.txt	AC	37 ms	9240 KiB
test-06.txt	AC	30 ms	9732 KiB
test-07.txt	AC	20 ms	9208 KiB
test-08.txt	AC	58 ms	11548 KiB
test-09.txt	AC	49 ms	13200 KiB
test-10.txt	AC	97 ms	20488 KiB
test-11.txt	AC	99 ms	20476 KiB
test-12.txt	AC	85 ms	20408 KiB
test-13.txt	AC	89 ms	20480 KiB
test-14.txt	AC	99 ms	20468 KiB
test-15.txt	AC	67 ms	20504 KiB
test-16.txt	AC	83 ms	20308 KiB
test-17.txt	AC	85 ms	20404 KiB
test-18.txt	AC	89 ms	20504 KiB
test-19.txt	AC	93 ms	20488 KiB
test-20.txt	AC	88 ms	20480 KiB
test-21.txt	AC	219 ms	20360 KiB
test-22.txt	AC	195 ms	20368 KiB
test-23.txt	AC	214 ms	20500 KiB
test-24.txt	AC	237 ms	20480 KiB
test-25.txt	AC	240 ms	20476 KiB
test-26.txt	AC	235 ms	20468 KiB
test-27.txt	AC	26 ms	3284 KiB
test-28.txt	AC	33 ms	18840 KiB
test-29.txt	AC	97 ms	20364 KiB