Submission #1163759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163759		javkhlantogs	Regions (IOI09_regions)	C++20	1 / 100	8053 ms	196608 KiB

regions

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> par,B;
vector<vector<ll>> A,pre;
vector<ll> vr;
vector<vector<pair<ll,ll>>> C;
vector<pair<ll,ll>> r;
ll cnt=0;
void dfs(ll u,ll p){
	r[u].first=cnt++;
	for(auto v:A[u]){
		if(v!=p) dfs(v,u);
	}
	r[u].second=cnt++;
	C[B[u]].push_back({r[u].first,r[u].second});
}
void dfs2(ll u,ll p,ll k){
	if(B[u]==p) k++;
	pre[vr[p]][B[u]]+=k;
	for(auto v:A[u]){
		if(v!=par[u]) dfs2(v,p,k);
	}
}
int main(){
	ll n,q,R,i,j,k,x,y,a,b,r1,r2,ans;
	cin>>n>>R>>q;
	par.resize(n+1);
	A.resize(n+1);
	B.resize(n+1);
	C.resize(R+1);
	r.resize(n+1);
	vr.resize(R+1);
	pre.resize(R+1,vector<ll>(R+1));
	cin>>x;
	B[1]=x;
	for(i=2 ; i<=n ; i++){
		cin>>par[i]>>x;
		A[i].push_back(par[i]);
		A[par[i]].push_back(i);
		B[i]=x;
	}
	dfs(1,1);
	ll id=0;
	for(i=1 ; i<=R ; i++){
		sort(C[i].rbegin(),C[i].rend());
		if(C[i].size()>=sqrt(n)){
			vr[i]=id++;
			dfs2(1,i,0);
		}
	}
	for(i=0 ; i<q ; i++){
		cin>>r1>>r2;
		ans=0;
		if(C[i].size()>=sqrt(n)){
			cout<<pre[vr[r1]][r2]<<"\n";
			continue;
		}
		for(auto v:C[r1]){
			ll ng1=C[r2].size();
			ll ok1=-1;
			while(ng1-ok1>1){
				ll mid=(ng1+ok1)/2;
				if(C[r2][mid].first>v.second) ok1=mid;
					else ng1=mid; 
			}
			ll ok2=ng1-1;
			ll ng2=C[r2].size();
			while(ng2-ok2>1){
				ll mid=(ng2+ok2)/2;
				if(C[r2][mid].first<v.first) ng2=mid;
					else ok2=mid; 
			}
			ans+=ok2-ng1+1;
		}
		cout<<ans<<endl;
	}
	return 0;
}

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