oj.uz

Submission #730357

# Submission time Handle Problem Language Result Execution time Memory
730357 2023-04-25T17:59:21 Z NintsiChkhaidze Regions (IOI09_regions) C++17
95 / 100
 6623 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=605,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 4 ms 5664 KB Output is correct
2 Correct 5 ms 5584 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 10 ms 5712 KB Output is correct
6 Correct 15 ms 5740 KB Output is correct
7 Correct 19 ms 5760 KB Output is correct
8 Correct 51 ms 5712 KB Output is correct
9 Correct 55 ms 6860 KB Output is correct
10 Correct 84 ms 6224 KB Output is correct
11 Correct 152 ms 6540 KB Output is correct
12 Correct 96 ms 7636 KB Output is correct
13 Correct 178 ms 6848 KB Output is correct
14 Correct 384 ms 7248 KB Output is correct
15 Correct 474 ms 15932 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1568 ms 15456 KB Output is correct
2 Correct 1768 ms 11020 KB Output is correct
3 Correct 3320 ms 27392 KB Output is correct
4 Correct 303 ms 7668 KB Output is correct
5 Correct 484 ms 12668 KB Output is correct
6 Correct 1546 ms 9544 KB Output is correct
7 Correct 2102 ms 10352 KB Output is correct
8 Correct 2648 ms 24888 KB Output is correct
9 Correct 4151 ms 17708 KB Output is correct
10 Correct 6548 ms 33040 KB Output is correct
11 Correct 6623 ms 17432 KB Output is correct
12 Correct 1832 ms 17292 KB Output is correct
13 Correct 2428 ms 21992 KB Output is correct
14 Correct 2808 ms 26676 KB Output is correct
15 Correct 4779 ms 37980 KB Output is correct
16 Correct 4186 ms 73680 KB Output is correct
17 Runtime error 127 ms 131072 KB Execution killed with signal 9