oj.uz

Submission #330428

# Submission time Handle Problem Language Result Execution time Memory
330428 2020-11-25T08:49:09 Z kshitij_sodani Regions (IOI09_regions) C++14
65 / 100
 8000 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(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 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 22 ms 19820 KB Output is correct
6 Correct 30 ms 19820 KB Output is correct
7 Correct 42 ms 19820 KB Output is correct
8 Correct 46 ms 19820 KB Output is correct
9 Correct 61 ms 20204 KB Output is correct
10 Correct 100 ms 20332 KB Output is correct
11 Correct 135 ms 20588 KB Output is correct
12 Correct 169 ms 21100 KB Output is correct
13 Correct 194 ms 20716 KB Output is correct
14 Correct 241 ms 21356 KB Output is correct
15 Correct 293 ms 23916 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8026 ms 24428 KB Time limit exceeded
2 Execution timed out 8063 ms 23276 KB Time limit exceeded
3 Execution timed out 8048 ms 26220 KB Time limit exceeded
4 Correct 290 ms 21484 KB Output is correct
5 Correct 416 ms 23020 KB Output is correct
6 Correct 1831 ms 24844 KB Output is correct
7 Correct 1952 ms 26096 KB Output is correct
8 Correct 1740 ms 33236 KB Output is correct
9 Correct 3024 ms 32492 KB Output is correct
10 Correct 5250 ms 44524 KB Output is correct
11 Correct 5889 ms 38952 KB Output is correct
12 Correct 6306 ms 30712 KB Output is correct
13 Correct 7159 ms 30900 KB Output is correct
14 Execution timed out 8026 ms 32364 KB Time limit exceeded
15 Execution timed out 8071 ms 35180 KB Time limit exceeded
16 Execution timed out 8039 ms 40428 KB Time limit exceeded
17 Execution timed out 8074 ms 40940 KB Time limit exceeded