oj.uz

Submission #330438

# Submission time Handle Problem Language Result Execution time Memory
330438 2020-11-25T09:06:29 Z kshitij_sodani Regions (IOI09_regions) C++14
90 / 100
 7785 ms 131076 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]>200){

		//	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]<=200){
			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 16 ms 23788 KB Output is correct
3 Correct 18 ms 23936 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 42 ms 24044 KB Output is correct
8 Correct 64 ms 23916 KB Output is correct
9 Correct 69 ms 24300 KB Output is correct
10 Correct 129 ms 24428 KB Output is correct
11 Correct 163 ms 24684 KB Output is correct
12 Correct 189 ms 25196 KB Output is correct
13 Correct 170 ms 24812 KB Output is correct
14 Correct 250 ms 25484 KB Output is correct
15 Correct 306 ms 28012 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1745 ms 28720 KB Output is correct
2 Correct 1603 ms 27760 KB Output is correct
3 Correct 3448 ms 30316 KB Output is correct
4 Correct 239 ms 25604 KB Output is correct
5 Correct 403 ms 27116 KB Output is correct
6 Correct 704 ms 30444 KB Output is correct
7 Correct 1602 ms 32084 KB Output is correct
8 Correct 1426 ms 41064 KB Output is correct
9 Correct 3497 ms 45548 KB Output is correct
10 Correct 3573 ms 108064 KB Output is correct
11 Runtime error 6788 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Correct 7785 ms 72148 KB Output is correct
13 Correct 5508 ms 72940 KB Output is correct
14 Correct 2961 ms 38420 KB Output is correct
15 Correct 3597 ms 39604 KB Output is correct
16 Runtime error 1978 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 3496 ms 47040 KB Output is correct