oj.uz

Submission #330432

# Submission time Handle Problem Language Result Execution time Memory
330432 2020-11-25T08:54:01 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 6206 ms 54132 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[25001];
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;
	}
	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]>300){
			for(int j=0;j<=r;j++){
				pre[i].pb(j);
			}
			cur=i;
			cot2=0;
			dfs2(0);
		}
	}
	//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]<=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 14 ms 19692 KB Output is correct
2 Correct 14 ms 19692 KB Output is correct
3 Correct 16 ms 19692 KB Output is correct
4 Correct 16 ms 19692 KB Output is correct
5 Correct 18 ms 19820 KB Output is correct
6 Correct 32 ms 19820 KB Output is correct
7 Correct 39 ms 19820 KB Output is correct
8 Correct 44 ms 19820 KB Output is correct
9 Correct 60 ms 20204 KB Output is correct
10 Correct 89 ms 20332 KB Output is correct
11 Correct 141 ms 20588 KB Output is correct
12 Correct 169 ms 21100 KB Output is correct
13 Correct 196 ms 20716 KB Output is correct
14 Correct 289 ms 21356 KB Output is correct
15 Correct 324 ms 23916 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2246 ms 24428 KB Output isn't correct
2 Incorrect 2484 ms 23348 KB Output isn't correct
3 Incorrect 3492 ms 26348 KB Output isn't correct
4 Correct 273 ms 21484 KB Output is correct
5 Correct 384 ms 23020 KB Output is correct
6 Incorrect 590 ms 26476 KB Output isn't correct
7 Incorrect 1507 ms 28012 KB Output isn't correct
8 Incorrect 1454 ms 36972 KB Output isn't correct
9 Incorrect 2916 ms 35200 KB Output isn't correct
10 Incorrect 3708 ms 54132 KB Output isn't correct
11 Incorrect 6206 ms 48364 KB Output isn't correct
12 Incorrect 1603 ms 30980 KB Output isn't correct
13 Incorrect 2292 ms 31084 KB Output isn't correct
14 Incorrect 2745 ms 34360 KB Output isn't correct
15 Incorrect 3786 ms 35500 KB Output isn't correct
16 Incorrect 3310 ms 40684 KB Output isn't correct
17 Incorrect 3631 ms 42816 KB Output isn't correct