oj.uz

Submission #330437

# Submission time Handle Problem Language Result Execution time Memory
330437 2020-11-25T09:06:10 Z kshitij_sodani Regions (IOI09_regions) C++14
100 / 100
 6606 ms 58164 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'

vector<int> adj[200001];
int it[200001];
int co[200001];
int st[200001];
int coo=0;
int endd[200001];
vector<int> ss[200001];
vector<int> tt[200001];
const int cc=300;
vector<int> ee[200001];
int cot[250001];
vector<llo> pre[200001];
void dfs(int no,int par2=-1,int levv=0){
	st[no]=coo;

	coo++;

	/*if(levv%cc==0){

	}*/
	ss[it[no]].pb(st[no]);
	tt[it[no]].pb(no);
	for(auto j:adj[no]){
		dfs(j,no,levv+1);
	}
	endd[no]=coo-1;
}
int cur=-1;
int cot2=0;

void dfs2(int no){
	if(it[no]==cur){
		cot2+=1;
	}
	//cout<<cot2<<",,"<<it[no]<<endl;
	pre[cur][it[no]]+=cot2;
	for(auto j:adj[no]){
		dfs2(j);
	}
	if(it[no]==cur){
		cot2-=1;
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,r,q;
	cin>>n>>r>>q;
	for(int i=0;i<n;i++){
		if(i==0){
			cin>>it[i];
		}
		else{
			int xx;
			cin>>xx>>it[i];
			xx--;
			adj[xx].pb(i);
		}
	}
	for(int i=0;i<n;i++){
		co[it[i]]++;
	}
	dfs(0);
	for(int i=1;i<=r;i++){
		if(co[i]>300){

		//	cout<<i<<"::"<<endl;
			
			for(int j=0;j<=r;j++){
				pre[i].pb(0);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		/*	for(auto j:pre[i]){
				cout<<j<<":";
			}
			cout<<endl;*/
		}
	}
	//int q;
	//cin>>q;
//	map<pair<int,int>,int> xx;
	while(q--){
		int aa,bb;
		cin>>aa>>bb;
		/*if(xx[{aa,bb}]){
			cout<<xx[{aa,bb}]<<endl;
			continue;
		}*/
		llo ans=0;
		//co[bb]>=300 or 
		if(co[aa]<=300){
			for(auto j:tt[aa]){
				ans+=(upper_bound(ss[bb].begin(),ss[bb].end(),endd[j])-lower_bound(ss[bb].begin(),ss[bb].end(),st[j]));
			}
		}
		else{
			ans=pre[aa][bb];
		}
		cout<<ans<<endl;
	//	xx[{aa,bb}]=ans;
	}














 
 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23788 KB Output is correct
2 Correct 17 ms 23788 KB Output is correct
3 Correct 20 ms 23788 KB Output is correct
4 Correct 22 ms 23788 KB Output is correct
5 Correct 26 ms 23916 KB Output is correct
6 Correct 40 ms 23916 KB Output is correct
7 Correct 42 ms 24044 KB Output is correct
8 Correct 53 ms 23916 KB Output is correct
9 Correct 85 ms 24300 KB Output is correct
10 Correct 114 ms 24428 KB Output is correct
11 Correct 139 ms 24684 KB Output is correct
12 Correct 197 ms 25196 KB Output is correct
13 Correct 286 ms 24812 KB Output is correct
14 Correct 325 ms 25452 KB Output is correct
15 Correct 383 ms 28012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2089 ms 28652 KB Output is correct
2 Correct 2350 ms 27460 KB Output is correct
3 Correct 3326 ms 30380 KB Output is correct
4 Correct 290 ms 25580 KB Output is correct
5 Correct 407 ms 27116 KB Output is correct
6 Correct 789 ms 30548 KB Output is correct
7 Correct 1332 ms 32032 KB Output is correct
8 Correct 1340 ms 41052 KB Output is correct
9 Correct 2713 ms 39308 KB Output is correct
10 Correct 4218 ms 58164 KB Output is correct
11 Correct 6606 ms 52296 KB Output is correct
12 Correct 1642 ms 35012 KB Output is correct
13 Correct 2701 ms 35180 KB Output is correct
14 Correct 3700 ms 38392 KB Output is correct
15 Correct 4058 ms 39744 KB Output is correct
16 Correct 4284 ms 44844 KB Output is correct
17 Correct 4254 ms 46940 KB Output is correct