oj.uz

답안 #434073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
434073 2021-06-20T14:41:53 Z rainboy Regions (IOI09_regions) C
35 / 100
 3232 ms 17136 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)