oj.uz

Submission #330441

# Submission time Handle Problem Language Result Execution time Memory
330441 2020-11-25T09:08:59 Z kshitij_sodani Regions (IOI09_regions) C++14
100 / 100
 5049 ms 53488 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];

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]>350){

		//	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]<=350){
			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 12 ms 19180 KB Output is correct
2 Correct 13 ms 19180 KB Output is correct
3 Correct 14 ms 19180 KB Output is correct
4 Correct 18 ms 19180 KB Output is correct
5 Correct 22 ms 19180 KB Output is correct
6 Correct 29 ms 19180 KB Output is correct
7 Correct 45 ms 19180 KB Output is correct
8 Correct 42 ms 19456 KB Output is correct
9 Correct 57 ms 19692 KB Output is correct
10 Correct 101 ms 19692 KB Output is correct
11 Correct 107 ms 20000 KB Output is correct
12 Correct 217 ms 20460 KB Output is correct
13 Correct 227 ms 20204 KB Output is correct
14 Correct 322 ms 20716 KB Output is correct
15 Correct 417 ms 23276 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2341 ms 23864 KB Output is correct
2 Correct 2843 ms 22756 KB Output is correct
3 Correct 3800 ms 25728 KB Output is correct
4 Correct 468 ms 20844 KB Output is correct
5 Correct 388 ms 22380 KB Output is correct
6 Correct 696 ms 25836 KB Output is correct
7 Correct 1529 ms 26208 KB Output is correct
8 Correct 1613 ms 36332 KB Output is correct
9 Correct 2630 ms 28704 KB Output is correct
10 Correct 4214 ms 53488 KB Output is correct
11 Correct 5049 ms 28696 KB Output is correct
12 Correct 1720 ms 30464 KB Output is correct
13 Correct 2231 ms 30496 KB Output is correct
14 Correct 3041 ms 33704 KB Output is correct
15 Correct 3412 ms 34860 KB Output is correct
16 Correct 3505 ms 40168 KB Output is correct
17 Correct 3394 ms 42428 KB Output is correct