Submission #330434

#	Time	Username	Problem	Language	Result	Execution time	Memory
330434		kshitij_sodani	Regions (IOI09_regions)	C++14	25 / 100	7325 ms	61780 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<llo> adj[200001];
llo it[200001];
llo co[200001];
llo st[200001];
llo coo=0;
llo endd[200001];
vector<llo> ss[200001];
vector<llo> tt[200001];
const llo cc=300;
vector<llo> ee[200001];
llo cot[250001];
vector<llo> pre[200001];
void dfs(llo no,llo par2=-1,llo 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;
}
llo cur=-1;
llo cot2=0;

void dfs2(llo no){
	if(it[no]==cur){
		cot2+=1;
	}
	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);
	llo n,r,q;
	cin>>n>>r>>q;
	for(llo i=0;i<n;i++){
		if(i==0){
			cin>>it[i];
		}
		else{
			llo xx;
			cin>>xx>>it[i];
			xx--;
			adj[xx].pb(i);
		}
	}
	for(llo i=0;i<n;i++){
		co[it[i]]++;
	}
	dfs(0);
	for(llo i=1;i<=r;i++){
		if(co[i]>300){
			for(llo j=0;j<=r;j++){
				pre[i].pb(j);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		}
	}
	//llo q;
	//cin>>q;
//	map<pair<llo,llo>,llo> xx;
	while(q--){
		llo 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]<=300){
			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: 10 / 85