oj.uz

Submission #74291

# Submission time Handle Problem Language Result Execution time Memory
74291 2018-08-30T22:35:43 Z Bruteforceman Regions (IOI09_regions) C++11
100 / 100
 6595 ms 75512 KB 
#include "bits/stdc++.h"
using namespace std;
int N, R, Q;
int a[200010], p[200010];
const int magic = 200;
const int chunk = 5 + (200000 / magic);
int ans[chunk][25001];
vector <int> g[200010];

int idx[25001];
int current;
int tot[25001];

void dfs(int x, int cnt) {
	cnt += (current == a[x]);
	if(a[x] != current) {
		ans[idx[current]][a[x]] += cnt;
	}
	for(auto i : g[x]) {
		dfs(i, cnt);
	}
} 

int in[200010];
int out[200010];
vector <int> v[25001];
vector <int> nodes[25001];
int cur;

void go(int x) {
	in[x] = ++cur;
	v[a[x]].emplace_back(in[x]);
	for(auto i : g[x]) {
		go(i);
	}
	out[x] = cur;
}
int count(int l, int r, int val) {
	return upper_bound(v[val].begin(), v[val].end(), r) - lower_bound(v[val].begin(), v[val].end(), l);
}

int main(int argc, char const *argv[])
{
	scanf("%d %d %d", &N, &R, &Q);
	for(int i = 1; i <= N; i++) {
		if(i == 1) scanf("%d", &a[i]);
		else scanf("%d %d", &p[i], &a[i]);
	}
	for(int i = 2; i <= N; i++) {
		g[p[i]].emplace_back(i);
	}
	for(int i = 1; i <= N; i++) {
		tot[a[i]] += 1;
		nodes[a[i]].emplace_back(i);
	}
	int now = 0;
	for(int i = 1; i <= R; i++) {
		if(tot[i] > magic) {
			current = i;
			idx[i] = now++; 
			dfs(1, 0);
		}
	}
	go(1);
	while(Q--) {
		int p, q;
		scanf("%d %d", &p, &q);
		if(tot[p] > magic) {
			printf("%d\n", ans[idx[p]][q]);
		} else {
			int res = 0;
			for(int i : nodes[p]) {
				res += count(in[i], out[i], q);
			}
			printf("%d\n", res);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main(int, const char**)':
regions.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &R, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:46:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i == 1) scanf("%d", &a[i]);
              ~~~~~^~~~~~~~~~~~~
regions.cpp:47:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d %d", &p[i], &a[i]);
        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6136 KB Output is correct
2 Correct 6 ms 6212 KB Output is correct
3 Correct 8 ms 6288 KB Output is correct
4 Correct 8 ms 6308 KB Output is correct
5 Correct 9 ms 6384 KB Output is correct
6 Correct 22 ms 6528 KB Output is correct
7 Correct 18 ms 6528 KB Output is correct
8 Correct 35 ms 6544 KB Output is correct
9 Correct 27 ms 6800 KB Output is correct
10 Correct 88 ms 6928 KB Output is correct
11 Correct 132 ms 7312 KB Output is correct
12 Correct 141 ms 7716 KB Output is correct
13 Correct 194 ms 7716 KB Output is correct
14 Correct 309 ms 8100 KB Output is correct
15 Correct 353 ms 10020 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 11672 KB Output is correct
2 Correct 1039 ms 11672 KB Output is correct
3 Correct 3238 ms 12720 KB Output is correct
4 Correct 194 ms 12720 KB Output is correct
5 Correct 317 ms 12720 KB Output is correct
6 Correct 472 ms 12720 KB Output is correct
7 Correct 1280 ms 12920 KB Output is correct
8 Correct 1137 ms 19092 KB Output is correct
9 Correct 2540 ms 22732 KB Output is correct
10 Correct 3174 ms 55220 KB Output is correct
11 Correct 5632 ms 75512 KB Output is correct
12 Correct 6595 ms 75512 KB Output is correct
13 Correct 3510 ms 75512 KB Output is correct
14 Correct 2888 ms 75512 KB Output is correct
15 Correct 4030 ms 75512 KB Output is correct
16 Correct 2570 ms 75512 KB Output is correct
17 Correct 3128 ms 75512 KB Output is correct