oj.uz

Submission #330435

# Submission time Handle Problem Language Result Execution time Memory
330435 2020-11-25T09:02:01 Z kshitij_sodani Regions (IOI09_regions) C++14
100 / 100
 7017 ms 61672 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<llo> adj[200001];
llo it[200001];
llo co[200001];
llo st[200001];
llo coo=0;
llo endd[200001];
vector<llo> ss[200001];
vector<llo> tt[200001];
const llo cc=300;
vector<llo> ee[200001];
llo cot[250001];
vector<llo> pre[200001];
void dfs(llo no,llo par2=-1,llo 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;
}
llo cur=-1;
llo cot2=0;

void dfs2(llo 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);
	llo n,r,q;
	cin>>n>>r>>q;
	for(llo i=0;i<n;i++){
		if(i==0){
			cin>>it[i];
		}
		else{
			llo xx;
			cin>>xx>>it[i];
			xx--;
			adj[xx].pb(i);
		}
	}
	for(llo i=0;i<n;i++){
		co[it[i]]++;
	}
	dfs(0);
	for(llo i=1;i<=r;i++){
		if(co[i]>300){

		//	cout<<i<<"::"<<endl;
			
			for(llo j=0;j<=r;j++){
				pre[i].pb(0);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		/*	for(auto j:pre[i]){
				cout<<j<<":";
			}
			cout<<endl;*/
		}
	}
	//llo q;
	//cin>>q;
//	map<pair<llo,llo>,llo> xx;
	while(q--){
		llo 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 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 18 ms 23916 KB Output is correct
4 Correct 19 ms 23916 KB Output is correct
5 Correct 22 ms 23916 KB Output is correct
6 Correct 39 ms 23916 KB Output is correct
7 Correct 45 ms 24044 KB Output is correct
8 Correct 36 ms 24044 KB Output is correct
9 Correct 67 ms 24556 KB Output is correct
10 Correct 101 ms 24556 KB Output is correct
11 Correct 139 ms 25196 KB Output is correct
12 Correct 159 ms 25708 KB Output is correct
13 Correct 206 ms 25580 KB Output is correct
14 Correct 294 ms 26348 KB Output is correct
15 Correct 312 ms 29184 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2062 ms 30316 KB Output is correct
2 Correct 2374 ms 29396 KB Output is correct
3 Correct 3329 ms 32492 KB Output is correct
4 Correct 297 ms 26348 KB Output is correct
5 Correct 395 ms 28012 KB Output is correct
6 Correct 629 ms 31724 KB Output is correct
7 Correct 1425 ms 33800 KB Output is correct
8 Correct 1278 ms 43116 KB Output is correct
9 Correct 3089 ms 43244 KB Output is correct
10 Correct 4333 ms 61672 KB Output is correct
11 Correct 7017 ms 57504 KB Output is correct
12 Correct 2313 ms 39148 KB Output is correct
13 Correct 3029 ms 39276 KB Output is correct
14 Correct 3223 ms 42844 KB Output is correct
15 Correct 4636 ms 43604 KB Output is correct
16 Correct 4327 ms 48616 KB Output is correct
17 Correct 3914 ms 51484 KB Output is correct