oj.uz

Submission #730354

# Submission time Handle Problem Language Result Execution time Memory
730354 2023-04-25T17:57:42 Z NintsiChkhaidze Regions (IOI09_regions) C++17
95 / 100
 6524 ms 131072 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];
vector <ll> ynull;
int r[N],tin[N],tout[N],id[25005];
int fen[N],B,r1,r2,timer;
ll 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 <ll> dfs(int x,int par, vector <ll> P){
	tin[x] = ++timer;
	vector <ll> 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 <ll> 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 3 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 11 ms 5712 KB Output is correct
6 Correct 18 ms 5840 KB Output is correct
7 Correct 39 ms 5712 KB Output is correct
8 Correct 43 ms 5712 KB Output is correct
9 Correct 51 ms 6864 KB Output is correct
10 Correct 96 ms 6224 KB Output is correct
11 Correct 156 ms 6480 KB Output is correct
12 Correct 150 ms 7504 KB Output is correct
13 Correct 215 ms 6864 KB Output is correct
14 Correct 351 ms 7248 KB Output is correct
15 Correct 424 ms 15824 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 17616 KB Output is correct
2 Correct 1465 ms 11132 KB Output is correct
3 Correct 3501 ms 27392 KB Output is correct
4 Correct 426 ms 7664 KB Output is correct
5 Correct 458 ms 12684 KB Output is correct
6 Correct 1711 ms 9552 KB Output is correct
7 Correct 2638 ms 10392 KB Output is correct
8 Correct 2857 ms 24828 KB Output is correct
9 Correct 4337 ms 17616 KB Output is correct
10 Correct 5870 ms 33064 KB Output is correct
11 Correct 6524 ms 17448 KB Output is correct
12 Correct 1680 ms 17292 KB Output is correct
13 Correct 2405 ms 21996 KB Output is correct
14 Correct 2269 ms 28680 KB Output is correct
15 Correct 4391 ms 37984 KB Output is correct
16 Correct 4719 ms 73676 KB Output is correct
17 Runtime error 142 ms 131072 KB Execution killed with signal 9