oj.uz

Submission #162867

# Submission time Handle Problem Language Result Execution time Memory
162867 2019-11-10T07:13:58 Z dolphingarlic Regions (IOI09_regions) C++14
90 / 100
 8000 ms 73620 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 7 ms 6188 KB Output is correct
2 Correct 8 ms 6136 KB Output is correct
3 Correct 9 ms 6136 KB Output is correct
4 Correct 11 ms 6136 KB Output is correct
5 Correct 15 ms 6136 KB Output is correct
6 Correct 28 ms 6264 KB Output is correct
7 Correct 24 ms 6264 KB Output is correct
8 Correct 24 ms 6264 KB Output is correct
9 Correct 38 ms 6652 KB Output is correct
10 Correct 104 ms 6696 KB Output is correct
11 Correct 159 ms 7032 KB Output is correct
12 Correct 181 ms 7544 KB Output is correct
13 Correct 200 ms 7416 KB Output is correct
14 Correct 309 ms 7800 KB Output is correct
15 Correct 301 ms 9848 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1790 ms 11380 KB Output is correct
2 Correct 1340 ms 10872 KB Output is correct
3 Correct 3577 ms 12496 KB Output is correct
4 Correct 276 ms 8008 KB Output is correct
5 Correct 342 ms 9232 KB Output is correct
6 Correct 555 ms 11176 KB Output is correct
7 Correct 1275 ms 12556 KB Output is correct
8 Correct 1232 ms 18904 KB Output is correct
9 Correct 3059 ms 22328 KB Output is correct
10 Correct 3221 ms 54644 KB Output is correct
11 Execution timed out 8069 ms 66072 KB Time limit exceeded
12 Execution timed out 8095 ms 30396 KB Time limit exceeded
13 Correct 5228 ms 37436 KB Output is correct
14 Correct 3648 ms 19668 KB Output is correct
15 Correct 4227 ms 21240 KB Output is correct
16 Correct 3360 ms 73620 KB Output is correct
17 Correct 3682 ms 25604 KB Output is correct