oj.uz

Submission #330430

# Submission time Handle Problem Language Result Execution time Memory
330430 2020-11-25T08:51:16 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 6202 ms 44524 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<int> 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;
		}*/
		int 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 13 ms 19692 KB Output is correct
2 Correct 14 ms 19692 KB Output is correct
3 Correct 14 ms 19820 KB Output is correct
4 Correct 19 ms 19692 KB Output is correct
5 Correct 19 ms 19820 KB Output is correct
6 Correct 30 ms 19820 KB Output is correct
7 Correct 38 ms 19820 KB Output is correct
8 Correct 44 ms 19820 KB Output is correct
9 Correct 93 ms 20352 KB Output is correct
10 Correct 105 ms 20332 KB Output is correct
11 Correct 137 ms 20588 KB Output is correct
12 Correct 171 ms 21100 KB Output is correct
13 Correct 234 ms 20716 KB Output is correct
14 Correct 276 ms 21356 KB Output is correct
15 Correct 346 ms 23916 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2145 ms 24452 KB Output isn't correct
2 Incorrect 2616 ms 23424 KB Output isn't correct
3 Incorrect 3578 ms 26272 KB Output isn't correct
4 Correct 306 ms 21484 KB Output is correct
5 Correct 364 ms 23168 KB Output is correct
6 Incorrect 619 ms 24684 KB Output isn't correct
7 Incorrect 1410 ms 26096 KB Output isn't correct
8 Incorrect 1150 ms 33260 KB Output isn't correct
9 Incorrect 2893 ms 32520 KB Output isn't correct
10 Incorrect 3501 ms 44524 KB Output isn't correct
11 Incorrect 6202 ms 38844 KB Output isn't correct
12 Incorrect 1667 ms 30776 KB Output isn't correct
13 Incorrect 2311 ms 30920 KB Output isn't correct
14 Incorrect 2937 ms 32412 KB Output isn't correct
15 Incorrect 3789 ms 35376 KB Output isn't correct
16 Incorrect 3581 ms 40584 KB Output isn't correct
17 Incorrect 3437 ms 41056 KB Output isn't correct