oj.uz

Submission #330423

# Submission time Handle Problem Language Result Execution time Memory
330423 2020-11-25T08:44:24 Z kshitij_sodani Regions (IOI09_regions) C++14
25 / 100
 6343 ms 54272 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 13 ms 19692 KB Output is correct
3 Correct 14 ms 19800 KB Output is correct
4 Correct 20 ms 19824 KB Output is correct
5 Correct 20 ms 19820 KB Output is correct
6 Correct 30 ms 19948 KB Output is correct
7 Correct 50 ms 19972 KB Output is correct
8 Correct 59 ms 20076 KB Output is correct
9 Correct 61 ms 20588 KB Output is correct
10 Correct 123 ms 20720 KB Output is correct
11 Correct 143 ms 21100 KB Output is correct
12 Correct 201 ms 21780 KB Output is correct
13 Correct 186 ms 21612 KB Output is correct
14 Correct 338 ms 22252 KB Output is correct
15 Correct 366 ms 24812 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1706 ms 26172 KB Output isn't correct
2 Incorrect 1560 ms 24892 KB Output isn't correct
3 Incorrect 2631 ms 30272 KB Output isn't correct
4 Correct 282 ms 23036 KB Output is correct
5 Correct 427 ms 25152 KB Output is correct
6 Incorrect 723 ms 26844 KB Output isn't correct
7 Incorrect 1253 ms 27248 KB Output isn't correct
8 Incorrect 1204 ms 37336 KB Output isn't correct
9 Incorrect 3319 ms 40648 KB Output isn't correct
10 Incorrect 4467 ms 54272 KB Output isn't correct
11 Incorrect 6343 ms 50764 KB Output isn't correct
12 Incorrect 1916 ms 35932 KB Output isn't correct
13 Incorrect 2882 ms 38028 KB Output isn't correct
14 Incorrect 3578 ms 40700 KB Output isn't correct
15 Incorrect 4392 ms 46564 KB Output isn't correct
16 Incorrect 3879 ms 52580 KB Output isn't correct
17 Incorrect 3567 ms 52336 KB Output isn't correct