oj.uz

Submission #330427

# Submission time Handle Problem Language Result Execution time Memory
330427 2020-11-25T08:46:46 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 5958 ms 44464 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*it[no];
	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 16 ms 19820 KB Output is correct
2 Correct 14 ms 19692 KB Output is correct
3 Correct 16 ms 19820 KB Output is correct
4 Correct 19 ms 19692 KB Output is correct
5 Correct 18 ms 19820 KB Output is correct
6 Correct 41 ms 19820 KB Output is correct
7 Correct 49 ms 19820 KB Output is correct
8 Correct 33 ms 19948 KB Output is correct
9 Correct 67 ms 20204 KB Output is correct
10 Correct 104 ms 20332 KB Output is correct
11 Correct 134 ms 20588 KB Output is correct
12 Correct 196 ms 21100 KB Output is correct
13 Correct 217 ms 20716 KB Output is correct
14 Correct 237 ms 21356 KB Output is correct
15 Correct 299 ms 23916 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1804 ms 24452 KB Output isn't correct
2 Incorrect 2341 ms 23320 KB Output isn't correct
3 Incorrect 3124 ms 26220 KB Output isn't correct
4 Correct 292 ms 21484 KB Output is correct
5 Correct 381 ms 23020 KB Output is correct
6 Incorrect 622 ms 24812 KB Output isn't correct
7 Incorrect 1245 ms 26220 KB Output isn't correct
8 Incorrect 1180 ms 33260 KB Output isn't correct
9 Incorrect 2781 ms 32492 KB Output isn't correct
10 Incorrect 3174 ms 44464 KB Output isn't correct
11 Incorrect 5958 ms 38944 KB Output isn't correct
12 Incorrect 1839 ms 30712 KB Output isn't correct
13 Incorrect 2347 ms 30956 KB Output isn't correct
14 Incorrect 3066 ms 32412 KB Output isn't correct
15 Incorrect 3894 ms 35308 KB Output isn't correct
16 Incorrect 3636 ms 40684 KB Output isn't correct
17 Incorrect 3031 ms 41048 KB Output isn't correct