Submission #434073

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434073	2021-06-20T14:41:53 Z	rainboy	Regions (IOI09_regions)	C	35 / 100	3232 ms	17136 KB

regions

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

#define N	200000
#define R	25000
#define K	450
#define S	450

int ta[N], tb[N];

int main() {
	static int pp[N], rr[N], qu[N], uu[N], dd[N], *iii[R], kk[R], ss[R], uuu[S][R], ddd[S][R];
	int n, r_, q, r, s, i, j;

	scanf("%d%d%d", &n, &r_, &q);
	for (i = 0; i < n; i++) {
		if (i > 0)
			scanf("%d", &pp[i]), pp[i]--;
		scanf("%d", &rr[i]), rr[i]--;
		kk[rr[i]]++;
	}
	for (i = n - 1; i >= 0; i--) {
		tb[i]++;
		if (i > 0)
			tb[pp[i]] += tb[i];
	}
	for (i = 0; i < n; i++) {
		if (i == 0)
			ta[i] = 0, tb[i] = 1;
		else
			ta[i] = tb[pp[i]], tb[pp[i]] += tb[i];
		qu[ta[i]] = i;
		tb[i] = ta[i] + 1;
	}
	for (r = 0, s = 0; r < r_; r++)
		if (kk[r] >= K) {
			ss[r] = s;
			for (i = 0; i < n; i++) {
				uu[i] = (i == 0 ? 0 : uu[pp[i]]) + (rr[i] == r);
				dd[i] = rr[i] == r;
			}
			for (i = n - 1; i > 0; i--)
				dd[pp[i]] += dd[i];
			for (i = 0; i < n; i++)
				uuu[s][rr[i]] += uu[i], ddd[s][rr[i]] += dd[i];
			s++;
		}
	for (r = 0; r < r_; r++)
		iii[r] = (int *) malloc(kk[r] * sizeof *iii[r]), kk[r] = 0;
	for (i = 0; i < n; i++) {
		r = rr[qu[i]];
		iii[r][kk[r]++] = qu[i];
	}
	while (q--) {
		int r1, r2;

		scanf("%d%d", &r1, &r2), r1--, r2--;
		if (kk[r1] >= K)
			printf("%d\n", uuu[ss[r1]][r2]);
		else if (kk[r2] >= K)
			printf("%d\n", ddd[ss[r2]][r1]);
		else {
			int h1, h2, ans, cnt;

			ans = 0, cnt = 0;
			for (h1 = 0, h2 = 0; h2 < kk[r2]; h2++) {
				j = iii[r2][h2];
				while (cnt && tb[qu[cnt - 1]] <= ta[j])
					cnt--;
				while (h1 < kk[r1] && ta[i = iii[r1][h1]] <= ta[j]) {
					if (ta[j] < tb[i])
						qu[cnt++] = i;
					h1++;
				}
				ans += cnt;
			}
			printf("%d\n", ans), fflush(stdout);
		}
	}
	return 0;
}

Compilation message

regions.c: In function 'main':
regions.c:15:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  scanf("%d%d%d", &n, &r_, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.c:18:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |    scanf("%d", &pp[i]), pp[i]--;
      |    ^~~~~~~~~~~~~~~~~~~
regions.c:19:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   scanf("%d", &rr[i]), rr[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
regions.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d", &r1, &r2), r1--, r2--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	200 KB	Output is correct
2	Correct	1 ms	200 KB	Output is correct
3	Correct	3 ms	200 KB	Output is correct
4	Correct	6 ms	200 KB	Output is correct
5	Correct	10 ms	200 KB	Output is correct
6	Correct	24 ms	328 KB	Output is correct
7	Correct	38 ms	328 KB	Output is correct
8	Correct	52 ms	328 KB	Output is correct
9	Correct	44 ms	328 KB	Output is correct
10	Correct	91 ms	456 KB	Output is correct
11	Correct	141 ms	584 KB	Output is correct
12	Correct	170 ms	712 KB	Output is correct
13	Correct	191 ms	840 KB	Output is correct
14	Correct	149 ms	1000 KB	Output is correct
15	Correct	228 ms	1224 KB	Output is correct

Subtask #2

20.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	32 ms	2752 KB	Time limit exceeded (wall clock)
2	Execution timed out	38 ms	2900 KB	Time limit exceeded (wall clock)
3	Execution timed out	34 ms	3232 KB	Time limit exceeded (wall clock)
4	Correct	271 ms	1096 KB	Output is correct
5	Correct	360 ms	1352 KB	Output is correct
6	Execution timed out	46 ms	5952 KB	Time limit exceeded (wall clock)
7	Execution timed out	32 ms	3960 KB	Time limit exceeded (wall clock)
8	Execution timed out	140 ms	12436 KB	Time limit exceeded (wall clock)
9	Correct	2231 ms	4308 KB	Output is correct
10	Execution timed out	159 ms	17136 KB	Time limit exceeded (wall clock)
11	Correct	3232 ms	5764 KB	Output is correct
12	Execution timed out	80 ms	7008 KB	Time limit exceeded (wall clock)
13	Execution timed out	66 ms	6996 KB	Time limit exceeded (wall clock)
14	Execution timed out	122 ms	10788 KB	Time limit exceeded (wall clock)
15	Execution timed out	67 ms	7860 KB	Time limit exceeded (wall clock)
16	Execution timed out	66 ms	7732 KB	Time limit exceeded (wall clock)
17	Execution timed out	128 ms	11044 KB	Time limit exceeded (wall clock)