oj.uz

Submission #330434

# Submission time Handle Problem Language Result Execution time Memory
330434 2020-11-25T08:56:06 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 7325 ms 61780 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;
	}
	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){
			for(llo j=0;j<=r;j++){
				pre[i].pb(j);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		}
	}
	//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 17 ms 23788 KB Output is correct
2 Correct 17 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 30 ms 23916 KB Output is correct
6 Correct 39 ms 23916 KB Output is correct
7 Correct 44 ms 24044 KB Output is correct
8 Correct 52 ms 24044 KB Output is correct
9 Correct 46 ms 24832 KB Output is correct
10 Correct 98 ms 24556 KB Output is correct
11 Correct 152 ms 25068 KB Output is correct
12 Correct 164 ms 25708 KB Output is correct
13 Correct 158 ms 25580 KB Output is correct
14 Correct 278 ms 26348 KB Output is correct
15 Correct 256 ms 29036 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2472 ms 30316 KB Output isn't correct
2 Incorrect 2751 ms 29396 KB Output isn't correct
3 Incorrect 3764 ms 32400 KB Output isn't correct
4 Correct 300 ms 26476 KB Output is correct
5 Correct 406 ms 28140 KB Output is correct
6 Incorrect 671 ms 31724 KB Output isn't correct
7 Incorrect 1517 ms 33644 KB Output isn't correct
8 Incorrect 1393 ms 43244 KB Output isn't correct
9 Incorrect 3458 ms 43072 KB Output isn't correct
10 Incorrect 4162 ms 61780 KB Output isn't correct
11 Incorrect 7325 ms 57152 KB Output isn't correct
12 Incorrect 2017 ms 39152 KB Output isn't correct
13 Incorrect 2700 ms 39420 KB Output isn't correct
14 Incorrect 3436 ms 42972 KB Output isn't correct
15 Incorrect 4395 ms 43616 KB Output isn't correct
16 Incorrect 4227 ms 48744 KB Output isn't correct
17 Incorrect 3930 ms 51388 KB Output isn't correct