Submission #330441

#	Time	Username	Problem	Language	Result	Execution time	Memory
330441		kshitij_sodani	Regions (IOI09_regions)	C++14	100 / 100	5049 ms	53488 KiB

regions

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'

vector<int> adj[200001];
int it[200001];
int co[200001];
int st[200001];
int coo=0;
int endd[200001];
vector<int> ss[200001];
vector<int> tt[200001];

vector<llo> pre[200001];
void dfs(int no,int par2=-1,int levv=0){
	st[no]=coo;

	coo++;

	/*if(levv%cc==0){

	}*/
	ss[it[no]].pb(st[no]);
	tt[it[no]].pb(no);
	for(auto j:adj[no]){
		dfs(j,no,levv+1);
	}
	endd[no]=coo-1;
}
int cur=-1;
int cot2=0;

void dfs2(int no){
	if(it[no]==cur){
		cot2+=1;
	}
	//cout<<cot2<<",,"<<it[no]<<endl;
	pre[cur][it[no]]+=cot2;
	for(auto j:adj[no]){
		dfs2(j);
	}
	if(it[no]==cur){
		cot2-=1;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=0;i<n;i++){
		if(i==0){
			cin>>it[i];
		}
		else{
			int xx;
			cin>>xx>>it[i];
			xx--;
			adj[xx].pb(i);
		}
	}
	for(int i=0;i<n;i++){
		co[it[i]]++;
	}
	dfs(0);
	for(int i=1;i<=r;i++){
		if(co[i]>350){

		//	cout<<i<<"::"<<endl;
			
			for(int j=0;j<=r;j++){
				pre[i].pb(0);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		/*	for(auto j:pre[i]){
				cout<<j<<":";
			}
			cout<<endl;*/
		}
	}
	//int q;
	//cin>>q;
//	map<pair<int,int>,int> xx;
	while(q--){
		int aa,bb;
		cin>>aa>>bb;
		/*if(xx[{aa,bb}]){
			cout<<xx[{aa,bb}]<<endl;
			continue;
		}*/
		llo ans=0;
		//co[bb]>=300 or 
		if(co[aa]<=350){
			for(auto j:tt[aa]){
				ans+=(upper_bound(ss[bb].begin(),ss[bb].end(),endd[j])-lower_bound(ss[bb].begin(),ss[bb].end(),st[j]));
			}
		}
		else{
			ans=pre[aa][bb];
		}
		cout<<ans<<endl;
	//	xx[{aa,bb}]=ans;
	}














 
 
	return 0;
}

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