oj.uz

Submission #330440

# Submission time Handle Problem Language Result Execution time Memory
330440 2020-11-25T09:08:15 Z kshitij_sodani Regions (IOI09_regions) C++14
100 / 100
 5568 ms 58240 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]>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 15 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 19 ms 23788 KB Output is correct
5 Correct 22 ms 23916 KB Output is correct
6 Correct 31 ms 23916 KB Output is correct
7 Correct 49 ms 24064 KB Output is correct
8 Correct 60 ms 23916 KB Output is correct
9 Correct 64 ms 24300 KB Output is correct
10 Correct 100 ms 24428 KB Output is correct
11 Correct 174 ms 24684 KB Output is correct
12 Correct 188 ms 25196 KB Output is correct
13 Correct 195 ms 25088 KB Output is correct
14 Correct 228 ms 25452 KB Output is correct
15 Correct 346 ms 28012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2266 ms 28564 KB Output is correct
2 Correct 2445 ms 27460 KB Output is correct
3 Correct 3460 ms 30380 KB Output is correct
4 Correct 360 ms 25580 KB Output is correct
5 Correct 377 ms 27116 KB Output is correct
6 Correct 701 ms 30548 KB Output is correct
7 Correct 1684 ms 30956 KB Output is correct
8 Correct 1293 ms 40940 KB Output is correct
9 Correct 2887 ms 33408 KB Output is correct
10 Correct 4186 ms 58240 KB Output is correct
11 Correct 5568 ms 33284 KB Output is correct
12 Correct 1470 ms 35064 KB Output is correct
13 Correct 3190 ms 35168 KB Output is correct
14 Correct 3581 ms 38424 KB Output is correct
15 Correct 4433 ms 39596 KB Output is correct
16 Correct 3581 ms 44844 KB Output is correct
17 Correct 4133 ms 47036 KB Output is correct