Submission #440169

#	Time	Username	Problem	Language	Result	Execution time	Memory
440169		dutch	Regions (IOI09_regions)	C++17	100 / 100	4145 ms	35104 KiB

regions

#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 / 15
• Subtask 2: 85 / 85