oj.uz

Submission #330429

# Submission time Handle Problem Language Result Execution time Memory
330429 2020-11-25T08:50:19 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 6937 ms 44396 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(no==cur){
		cot2+=1;
	}
	pre[cur][it[no]]+=cot2;
	for(auto j:adj[no]){
		dfs2(j);
	}
	if(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 14 ms 19692 KB Output is correct
2 Correct 12 ms 19692 KB Output is correct
3 Correct 14 ms 19692 KB Output is correct
4 Correct 18 ms 19692 KB Output is correct
5 Correct 20 ms 19820 KB Output is correct
6 Correct 42 ms 19820 KB Output is correct
7 Correct 50 ms 19820 KB Output is correct
8 Correct 48 ms 19820 KB Output is correct
9 Correct 78 ms 20204 KB Output is correct
10 Correct 116 ms 20332 KB Output is correct
11 Correct 124 ms 20588 KB Output is correct
12 Correct 201 ms 21100 KB Output is correct
13 Correct 232 ms 20716 KB Output is correct
14 Correct 362 ms 21484 KB Output is correct
15 Correct 292 ms 23916 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 2131 ms 24452 KB Output isn't correct
2 Incorrect 2612 ms 23320 KB Output isn't correct
3 Incorrect 3631 ms 26272 KB Output isn't correct
4 Correct 273 ms 21632 KB Output is correct
5 Correct 391 ms 23020 KB Output is correct
6 Incorrect 634 ms 24724 KB Output isn't correct
7 Incorrect 1637 ms 26124 KB Output isn't correct
8 Incorrect 1425 ms 33236 KB Output isn't correct
9 Incorrect 3513 ms 32492 KB Output isn't correct
10 Incorrect 4035 ms 44396 KB Output isn't correct
11 Incorrect 6937 ms 38920 KB Output isn't correct
12 Incorrect 1548 ms 30716 KB Output isn't correct
13 Incorrect 2427 ms 30828 KB Output isn't correct
14 Incorrect 3724 ms 32444 KB Output isn't correct
15 Incorrect 4257 ms 35232 KB Output isn't correct
16 Incorrect 3408 ms 40536 KB Output isn't correct
17 Incorrect 3449 ms 41072 KB Output isn't correct