Submission #434075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434075	2021-06-20T14:43:36 Z	rainboy	Regions (IOI09_regions)	C	100 / 100	2923 ms	17180 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]), fflush(stdout);
		else if (kk[r2] >= K)
			printf("%d\n", ddd[ss[r2]][r1]), fflush(stdout);
		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	4 ms	200 KB	Output is correct
6	Correct	26 ms	328 KB	Output is correct
7	Correct	46 ms	328 KB	Output is correct
8	Correct	29 ms	328 KB	Output is correct
9	Correct	56 ms	328 KB	Output is correct
10	Correct	76 ms	452 KB	Output is correct
11	Correct	114 ms	640 KB	Output is correct
12	Correct	150 ms	712 KB	Output is correct
13	Correct	165 ms	840 KB	Output is correct
14	Correct	164 ms	968 KB	Output is correct
15	Correct	266 ms	1224 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	854 ms	2752 KB	Output is correct
2	Correct	1071 ms	2880 KB	Output is correct
3	Correct	1904 ms	3136 KB	Output is correct
4	Correct	171 ms	1104 KB	Output is correct
5	Correct	401 ms	1352 KB	Output is correct
6	Correct	620 ms	5952 KB	Output is correct
7	Correct	1088 ms	3904 KB	Output is correct
8	Correct	962 ms	12484 KB	Output is correct
9	Correct	1847 ms	4192 KB	Output is correct
10	Correct	2439 ms	17180 KB	Output is correct
11	Correct	2923 ms	5772 KB	Output is correct
12	Correct	1141 ms	6988 KB	Output is correct
13	Correct	1756 ms	6976 KB	Output is correct
14	Correct	1926 ms	10816 KB	Output is correct
15	Correct	2715 ms	7724 KB	Output is correct
16	Correct	2430 ms	7744 KB	Output is correct
17	Correct	2542 ms	10968 KB	Output is correct