oj.uz

Submission #440169

# Submission time Handle Problem Language Result Execution time Memory
440169 2021-07-01T16:46:19 Z dutch Regions (IOI09_regions) C++17
100 / 100
 4145 ms 35104 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 2e5, MAXK = 2.5e4, SQRT = 350;
 
int k[MAXN], cnt[MAXK], t[MAXN], s[MAXN], dfsTimer = 0, cur, c, lg[MAXK];
vector<int> g[MAXN], a[MAXN], res[MAXK], ord[MAXK];
 
void dfs0(int u){
	t[u] = dfsTimer++, s[u] = 1;
	ord[k[u]].push_back(t[u]);
	for(int v : g[u]) dfs0(v), s[u] += s[v];
}
 
void dfs1(int u){
	if(k[u] == cur) ++c;
	res[cur][k[u]] += c;
	for(int v : g[u]) dfs1(v);
	if(k[u] == cur) --c;
}

int bs(int v, int val){
	int x = -1;
	for(int y=1<<lg[v]; y/=2; ) if(x+y < (int)ord[v].size() && ord[v][x+y] <= val) x += y;
	return x;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
 
	int n, r, q, x, y; cin >> n >> r >> q;
 
	for(int i=0, j; i<n; ++i){
		if(i) cin >> j, g[j-1].push_back(i);
		cin >> k[i], a[--k[i]].push_back(i);
	}
 
	dfs0(0);
 
	for(int i=0; i<r; ++i){
		while((1 << lg[i]) <= (int)a[i].size()) ++lg[i];
		if(a[i].size() < SQRT) continue;
		cur = i, c = 0;
		res[i].resize(r);
		dfs1(0);
	}
 
	while(q--){
		cin >> x >> y; --x, --y;
		if(a[x].size() < SQRT){
			int ans = 0;
			for(int u : a[x]){
				ans += bs(y, t[u]+s[u]-1) - bs(y, t[u]-1);
			}
			cout << ans << endl;
		}else{
			cout << res[x][y] << endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10824 KB Output is correct
2 Correct 8 ms 10788 KB Output is correct
3 Correct 9 ms 10824 KB Output is correct
4 Correct 11 ms 10800 KB Output is correct
5 Correct 14 ms 10824 KB Output is correct
6 Correct 30 ms 10952 KB Output is correct
7 Correct 41 ms 10952 KB Output is correct
8 Correct 41 ms 10952 KB Output is correct
9 Correct 61 ms 11336 KB Output is correct
10 Correct 101 ms 11392 KB Output is correct
11 Correct 92 ms 11720 KB Output is correct
12 Correct 151 ms 12232 KB Output is correct
13 Correct 184 ms 11852 KB Output is correct
14 Correct 313 ms 12488 KB Output is correct
15 Correct 324 ms 15060 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1519 ms 15528 KB Output is correct
2 Correct 1724 ms 14372 KB Output is correct
3 Correct 2756 ms 17216 KB Output is correct
4 Correct 286 ms 12536 KB Output is correct
5 Correct 361 ms 14152 KB Output is correct
6 Correct 643 ms 15476 KB Output is correct
7 Correct 1216 ms 16288 KB Output is correct
8 Correct 1222 ms 23856 KB Output is correct
9 Correct 2292 ms 20364 KB Output is correct
10 Correct 2883 ms 35104 KB Output is correct
11 Correct 4145 ms 20288 KB Output is correct
12 Correct 1417 ms 21752 KB Output is correct
13 Correct 1733 ms 21952 KB Output is correct
14 Correct 2847 ms 23412 KB Output is correct
15 Correct 3499 ms 26192 KB Output is correct
16 Correct 3820 ms 31612 KB Output is correct
17 Correct 3423 ms 31952 KB Output is correct