Submission #1163399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163399		javkhlantogs	Regions (IOI09_regions)	C++20	85 / 100	8051 ms	39440 KiB

regions

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> par,B;
vector<vector<ll>> A,D;
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});
	D[B[u]].push_back(r[u].first);
}
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);
	D.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());
		sort(D[i].begin(),D[i].end());
	}
	for(i=0 ; i<q ; i++){
		cin>>r1>>r2;
		ans=0;
		for(auto v:C[r1]){
			ans+=lower_bound(D[r2].begin(),D[r2].end(),v.second)-lower_bound(D[r2].begin(),D[r2].end(),v.first);
		}
		cout<<ans<<endl;
	}
	return 0;
}

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