Submission #496084

#	Time	Username	Problem	Language	Result	Execution time	Memory
496084		mosiashvililuka	Regions (IOI09_regions)	C++14	100 / 100	3097 ms	87576 KiB

regions

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,f[200009],k[200009],T=167,K[200009],F[200009],TT,lf[200009],rg[200009],tim,C,D,lef,rig,mid;
//int ans[630][25002],ZX;
int ans[1202][25002],ZX;
vector <int> v[200009];
vector <pair <int, int> > vv[200009];
void dfs(int q, int w){
	tim++;
	lf[q]=rg[q]=tim;
	int qw=vv[f[q]].size();
	vv[f[q]].push_back(make_pair(lf[q],0));
	for(int h=1; h<=TT; h++){
		ans[h][f[q]]+=k[h];
	}
	if(F[f[q]]!=0) k[F[f[q]]]++;
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
		if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
	}
	vv[f[q]][qw].second=rg[q];
	if(F[f[q]]!=0) k[F[f[q]]]--;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>zx>>tes;
	cin>>f[1];
	for(i=2; i<=a; i++){
		cin>>c>>f[i];
		v[c].push_back(i);
	}
	for(i=1; i<=a; i++){
		K[f[i]]++;
	}
	TT=0;
	for(i=1; i<=a; i++){
		if(K[i]>T){
			TT++;F[i]=TT;
		}
	}
	dfs(1,0);
	for(t=1; t<=tes; t++){
		cin>>c>>d;
		if(vv[c].size()>T){
			cout<<ans[F[c]][d]<<endl;
		}else{
			C=vv[c].size();D=vv[d].size();ZX=0;
			for(vector <pair <int, int> >::iterator it=vv[c].begin(); it!=vv[c].end(); it++){
				lef=-1;rig=D;
				while(lef+1<rig){
					mid=((lef+rig)>>1);
					if(vv[d][mid].first>=(*it).first){
						rig=mid;
					}else{
						lef=mid;
					}
				}
				ii=rig;
				lef=ii-1;rig=D;
				while(lef+1<rig){
					mid=((lef+rig)>>1);
					if(vv[d][mid].first<=(*it).second){
						lef=mid;
					}else{
						rig=mid;
					}
				}
				jj=lef;
				ZX+=(jj-ii+1);
			}
			cout<<ZX<<endl;
		}
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |   if(vv[c].size()>T){
      |      ~~~~~~~~~~~~^~

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