oj.uz

Submission #730359

# Submission time Handle Problem Language Result Execution time Memory
730359 2023-04-25T18:01:46 Z NintsiChkhaidze Regions (IOI09_regions) C++17
90 / 100
 8000 ms 108204 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define ll long long
using namespace std;
 
const int N = 2e5+5,Bl=505,C = 200000/(Bl - 5) + 5;
 
vector <int> v[N],st[25005],ynull;
int r[N],tin[N],tout[N],id[25005];
int fen[N],B,r1,r2,timer;
int k[C][25005],DP[C][25005],ans;
bool big[25005];
 
int get(int idx){
	int s=0;
	while(idx){
		s+=fen[idx];
		idx -= (idx&(-idx));
	}
	return s;
}
void upd(int idx,int val){
	while (idx <= 200000){
		fen[idx] += val;
		idx += (idx & (-idx));
	}
}
vector <int> dfs(int x,int par, vector <int> P){
	tin[x] = ++timer;
	vector <int> vec = ynull,Pnew = ynull;
 
	if (x != 1){
		for (int i=0;i<B;i++) Pnew[i] += P[i];
		if (big[r[par]]) Pnew[id[r[par]] - 1]++;
	}
	vector <int> o;
	for (int to: v[x])
		if (to != par) {
			o = dfs(to,x,Pnew);
			for (int i = 0; i < B; i++) vec[i] += o[i];
			if (big[r[to]]) vec[id[r[to]] - 1]++;
		}
 
	for (int i=0;i<B;i++){
		k[i+1][r[x]] += vec[i];
		DP[i+1][r[x]] += Pnew[i];
	}
 
	tout[x] = timer;
	return vec;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int n,R,q;
	cin>>n>>R>>q;
 
	cin>>r[1]; st[r[1]].pb(1);
	for(int i=2;i<=n;i++){
		cin>>r1>>r[i];
		st[r[i]].pb(i);
		v[r1].pb(i);
		v[i].pb(r1);
	}
	
	B = 0;
	for (int i = 1; i <= R; i++){
		if ((int)st[i].size() > Bl){
			++B;
			id[i] = B; 
			big[i] = 1; 
		}
	}
	
	for (int i=0;i<B;i++) ynull.pb(0);
	dfs(1,1,ynull);
	while (q--){
		cin>>r1>>r2;
		if (!big[r1] && !big[r2]){
			ans=0;
			for (int x: st[r2]) upd(tin[x],1);
			for (int x: st[r1]) ans += get(tout[x]) - get(tin[x] - 1);
			for (int x: st[r2]) upd(tin[x],-1);
			cout<<ans<<endl;
		}else if (big[r2]){
			cout<<k[id[r2]][r1]<<endl;
		}else{
			cout<<DP[id[r1]][r2]<<endl;
		}
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 4 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 7 ms 5584 KB Output is correct
5 Correct 8 ms 5712 KB Output is correct
6 Correct 22 ms 5840 KB Output is correct
7 Correct 30 ms 5712 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 53 ms 6864 KB Output is correct
10 Correct 106 ms 6224 KB Output is correct
11 Correct 135 ms 6480 KB Output is correct
12 Correct 159 ms 7540 KB Output is correct
13 Correct 244 ms 6864 KB Output is correct
14 Correct 349 ms 7248 KB Output is correct
15 Correct 432 ms 15840 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1708 ms 15504 KB Output is correct
2 Correct 1664 ms 10828 KB Output is correct
3 Correct 3109 ms 22452 KB Output is correct
4 Correct 400 ms 7632 KB Output is correct
5 Correct 502 ms 12668 KB Output is correct
6 Correct 1726 ms 9560 KB Output is correct
7 Correct 2791 ms 10452 KB Output is correct
8 Correct 2654 ms 24792 KB Output is correct
9 Correct 4420 ms 17720 KB Output is correct
10 Execution timed out 8037 ms 33096 KB Time limit exceeded
11 Execution timed out 8055 ms 17444 KB Time limit exceeded
12 Correct 2374 ms 17044 KB Output is correct
13 Correct 3433 ms 21756 KB Output is correct
14 Correct 3526 ms 23892 KB Output is correct
15 Correct 6481 ms 37600 KB Output is correct
16 Correct 5578 ms 73292 KB Output is correct
17 Correct 5637 ms 108204 KB Output is correct