oj.uz

Submission #496084

# Submission time Handle Problem Language Result Execution time Memory
496084 2021-12-20T15:22:00 Z mosiashvililuka Regions (IOI09_regions) C++14
100 / 100
 3097 ms 87576 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9636 KB Output is correct
2 Correct 6 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 9 ms 9672 KB Output is correct
5 Correct 12 ms 9672 KB Output is correct
6 Correct 23 ms 9800 KB Output is correct
7 Correct 46 ms 9800 KB Output is correct
8 Correct 38 ms 9800 KB Output is correct
9 Correct 53 ms 10484 KB Output is correct
10 Correct 88 ms 10184 KB Output is correct
11 Correct 113 ms 10568 KB Output is correct
12 Correct 119 ms 11268 KB Output is correct
13 Correct 217 ms 10696 KB Output is correct
14 Correct 266 ms 11584 KB Output is correct
15 Correct 242 ms 16388 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 749 ms 16080 KB Output is correct
2 Correct 913 ms 14156 KB Output is correct
3 Correct 1231 ms 19224 KB Output is correct
4 Correct 166 ms 11664 KB Output is correct
5 Correct 391 ms 14152 KB Output is correct
6 Correct 567 ms 14732 KB Output is correct
7 Correct 863 ms 16892 KB Output is correct
8 Correct 918 ms 25920 KB Output is correct
9 Correct 1679 ms 26180 KB Output is correct
10 Correct 2690 ms 86444 KB Output is correct
11 Correct 3097 ms 77596 KB Output is correct
12 Correct 1850 ms 60596 KB Output is correct
13 Correct 2175 ms 61596 KB Output is correct
14 Correct 2464 ms 56320 KB Output is correct
15 Correct 2889 ms 86500 KB Output is correct
16 Correct 2841 ms 87576 KB Output is correct
17 Correct 2857 ms 72212 KB Output is correct