Submission #1163736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163736		javkhlantogs	Regions (IOI09_regions)	C++17	80 / 100	8080 ms	36856 KiB

regions

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> par,B;
vector<vector<ll>> A;
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});
}
int main(){
	ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
	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);
	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);
	for(i=1 ; i<=R ; i++){
		sort(C[i].rbegin(),C[i].rend());
	}
	for(i=0 ; i<q ; i++){
		cin>>r1>>r2;
		ans=0;
		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: 15 / 15
• Subtask 2: 65 / 85