Submission #1305887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305887		coolboy19521	Regions (IOI09_regions)	C++20	100 / 100	3292 ms	32624 KiB

regions

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=2e5+20,mxm=25000+20,mxb=450;

int r[mxn],cid[mxm],t,tin[mxn],tout[mxn];
vector<int>aj[mxn],cm[mxm],tns[mxm];
vector<vector<int>>prc;

void dfs(int u,int s,int c){
	if(r[u]==s)c++;
	else prc.back()[r[u]]+=c;
	for(int v:aj[u])dfs(v,s,c);
}

void tour(int u){
	tin[u]=++t;
	tns[r[u]].push_back(tin[u]);
	for(int v:aj[u])tour(v);
	tout[u]=t;
}

int main(){
	int N,R,Q;cin>>N>>R>>Q;
	cin>>r[1];
	cm[r[1]].push_back(1);
	FOR(i,2,N+1){
		int p;cin>>p>>r[i];
		aj[p].push_back(i);
		cm[r[i]].push_back(i);
	}
	int ls=0;
	FOR(i,1,R+1)if(cm[i].size()>=mxb){
		cid[i]=ls++;
		prc.push_back(vector<int>(R+1));
		dfs(1,i,0);
	}
	tour(1);
	REP(Q){
		int a,b;cin>>a>>b;
		if(cm[a].size()>=mxb)cout<<prc[cid[a]][b]<<endl;
		else{
			int ans=0;
			for(int v:cm[a])ans+=upper_bound(begin(tns[b]),end(tns[b]),tout[v])-lower_bound(begin(tns[b]),end(tns[b]),tin[v]);
			cout<<ans<<endl;
		}
	}
}

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