oj.uz

Submission #330420

# Submission time Handle Problem Language Result Execution time Memory
330420 2020-11-25T08:43:42 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 6509 ms 54376 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(i);
		}
	}
	//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 14 ms 19692 KB Output is correct
3 Correct 15 ms 19692 KB Output is correct
4 Correct 17 ms 19820 KB Output is correct
5 Correct 20 ms 19820 KB Output is correct
6 Correct 32 ms 19980 KB Output is correct
7 Correct 39 ms 20124 KB Output is correct
8 Correct 48 ms 20076 KB Output is correct
9 Correct 76 ms 20588 KB Output is correct
10 Correct 93 ms 20800 KB Output is correct
11 Correct 144 ms 21180 KB Output is correct
12 Correct 209 ms 21740 KB Output is correct
13 Correct 246 ms 21664 KB Output is correct
14 Correct 297 ms 22124 KB Output is correct
15 Correct 354 ms 24896 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1415 ms 26296 KB Output isn't correct
2 Incorrect 1736 ms 24904 KB Output isn't correct
3 Incorrect 2592 ms 30264 KB Output isn't correct
4 Correct 365 ms 23136 KB Output is correct
5 Correct 436 ms 25140 KB Output is correct
6 Incorrect 816 ms 26784 KB Output isn't correct
7 Incorrect 1006 ms 27304 KB Output isn't correct
8 Incorrect 1293 ms 37300 KB Output isn't correct
9 Incorrect 2656 ms 40712 KB Output isn't correct
10 Incorrect 3861 ms 54376 KB Output isn't correct
11 Incorrect 6509 ms 50768 KB Output isn't correct
12 Incorrect 1860 ms 35720 KB Output isn't correct
13 Incorrect 2815 ms 37956 KB Output isn't correct
14 Incorrect 3565 ms 40720 KB Output isn't correct
15 Incorrect 4457 ms 46412 KB Output isn't correct
16 Incorrect 5176 ms 52388 KB Output isn't correct
17 Incorrect 4207 ms 52340 KB Output isn't correct