Submission #730323

#	Time	Username	Problem	Language	Result	Execution time	Memory
730323		NintsiChkhaidze	Regions (IOI09_regions)	C++17	55 / 100	5819 ms	131072 KiB

regions

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;

const int N = 2e5+5,Bl=505;

vector <int> v[N],st[25005];
int r[N],tin[N],tout[N],cnt[N],timer,id[N],rev[N],dp[N][505];
int fen[N],B,k[25005][505],DP[505][N];
bool big[N],small[N];

int get(int idx){
	int s=0;
	while(idx){
		s+=fen[idx];
		idx -= (idx&(-idx));
	}
	return s;
}
void upd(int idx,int val){
	while (idx <= 200000){
		fen[idx] += val;
		idx += (idx & (-idx));
	}
}
void dfs(int x,int par){
	tin[x] = ++timer;

	if (x != 1){
		for (int i = 1; i <= B; i++)
			DP[i][x] += DP[i][par];
		if (big[r[par]])
			DP[id[r[par]]][x]++;
	}

	for (int to: v[x])
		if (to != par) {
			dfs(to,x);
			for (int i = 1; i <= B; i++)
				dp[x][i] += dp[to][i];
			if (big[r[to]]) dp[x][id[r[to]]]++;
		}

	for (int i = 1; i <= B; i++)
		k[r[x]][i] += dp[x][i];

	tout[x] = timer;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,R,q;
	cin>>n>>R>>q;

	cin>>r[1]; cnt[r[1]]++; st[r[1]].pb(1);
	for(int i=2;i<=n;i++){
		int p;
		cin>>p>>r[i];
		cnt[r[i]]++; st[r[i]].pb(i);
		v[p].pb(i);
		v[i].pb(p);
	}
	
	B = 0;
	for (int i = 1; i <= R; i++){
		if (cnt[i] > Bl){
			++B;
			id[i] = B; 
			big[i] = 1; 
		}else{
			small[i] = 1;
		}
	}

	dfs(1,1);
	while (q--){
		int r1,r2,ans=0;
		cin>>r1>>r2;

		if (small[r1] && small[r2]){
			for (int x: st[r2]) upd(tin[x],1);
			for (int x: st[r1]) ans += get(tout[x]) - get(tin[x] - 1);
			for (int x: st[r2]) upd(tin[x],-1);
			cout<<ans<<endl;
		}else if (big[r2]){
			cout<<k[r1][id[r2]]<<endl;
		}else{
			for (int x: st[r2])
				ans += DP[id[r1]][x];
			cout<<ans<<endl;
		}
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85