oj.uz

Submission #730360

# Submission time Handle Problem Language Result Execution time Memory
730360 2023-04-25T18:02:08 Z NintsiChkhaidze Regions (IOI09_regions) C++17
95 / 100
 8000 ms 99776 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=655,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 6 ms 5584 KB Output is correct
4 Correct 9 ms 5584 KB Output is correct
5 Correct 15 ms 5584 KB Output is correct
6 Correct 18 ms 5840 KB Output is correct
7 Correct 28 ms 5712 KB Output is correct
8 Correct 35 ms 5712 KB Output is correct
9 Correct 65 ms 6864 KB Output is correct
10 Correct 124 ms 6216 KB Output is correct
11 Correct 157 ms 6480 KB Output is correct
12 Correct 180 ms 7668 KB Output is correct
13 Correct 177 ms 6904 KB Output is correct
14 Correct 332 ms 7280 KB Output is correct
15 Correct 495 ms 15856 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1974 ms 14036 KB Output is correct
2 Correct 2494 ms 10716 KB Output is correct
3 Correct 3402 ms 22452 KB Output is correct
4 Correct 486 ms 7612 KB Output is correct
5 Correct 701 ms 12664 KB Output is correct
6 Correct 1896 ms 9476 KB Output is correct
7 Correct 3148 ms 10456 KB Output is correct
8 Correct 3015 ms 24916 KB Output is correct
9 Correct 4648 ms 17612 KB Output is correct
10 Correct 6946 ms 33136 KB Output is correct
11 Execution timed out 8026 ms 17400 KB Time limit exceeded
12 Correct 2431 ms 17052 KB Output is correct
13 Correct 3599 ms 21748 KB Output is correct
14 Correct 4417 ms 22852 KB Output is correct
15 Correct 6036 ms 37600 KB Output is correct
16 Correct 5570 ms 73296 KB Output is correct
17 Correct 5914 ms 99776 KB Output is correct