oj.uz

Submission #330439

# Submission time Handle Problem Language Result Execution time Memory
330439 2020-11-25T09:07:59 Z kshitij_sodani Regions (IOI09_regions) C++14
100 / 100
 5230 ms 58252 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]>400){

		//	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]<=400){
			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 18 ms 23788 KB Output is correct
4 Correct 20 ms 23788 KB Output is correct
5 Correct 24 ms 23916 KB Output is correct
6 Correct 34 ms 23916 KB Output is correct
7 Correct 44 ms 23916 KB Output is correct
8 Correct 52 ms 23916 KB Output is correct
9 Correct 61 ms 24300 KB Output is correct
10 Correct 85 ms 24428 KB Output is correct
11 Correct 124 ms 24684 KB Output is correct
12 Correct 179 ms 25196 KB Output is correct
13 Correct 199 ms 24812 KB Output is correct
14 Correct 291 ms 25580 KB Output is correct
15 Correct 306 ms 28012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1975 ms 28564 KB Output is correct
2 Correct 2270 ms 27500 KB Output is correct
3 Correct 3430 ms 30380 KB Output is correct
4 Correct 319 ms 25708 KB Output is correct
5 Correct 487 ms 27148 KB Output is correct
6 Correct 753 ms 30548 KB Output is correct
7 Correct 1699 ms 30268 KB Output is correct
8 Correct 1412 ms 41076 KB Output is correct
9 Correct 2975 ms 33408 KB Output is correct
10 Correct 3782 ms 58252 KB Output is correct
11 Correct 5230 ms 33168 KB Output is correct
12 Correct 1694 ms 35076 KB Output is correct
13 Correct 2461 ms 35088 KB Output is correct
14 Correct 2951 ms 38312 KB Output is correct
15 Correct 4623 ms 39616 KB Output is correct
16 Correct 4551 ms 44856 KB Output is correct
17 Correct 4543 ms 47256 KB Output is correct