oj.uz

Submission #730366

# Submission time Handle Problem Language Result Execution time Memory
730366 2023-04-25T18:05:17 Z NintsiChkhaidze Regions (IOI09_regions) C++17
100 / 100
 6037 ms 99784 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=635,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 8 ms 5584 KB Output is correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 28 ms 5748 KB Output is correct
7 Correct 30 ms 5712 KB Output is correct
8 Correct 45 ms 5712 KB Output is correct
9 Correct 52 ms 6864 KB Output is correct
10 Correct 87 ms 6224 KB Output is correct
11 Correct 154 ms 6528 KB Output is correct
12 Correct 179 ms 7668 KB Output is correct
13 Correct 234 ms 6864 KB Output is correct
14 Correct 406 ms 7320 KB Output is correct
15 Correct 487 ms 15812 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1753 ms 14040 KB Output is correct
2 Correct 1756 ms 10852 KB Output is correct
3 Correct 3403 ms 22440 KB Output is correct
4 Correct 425 ms 7652 KB Output is correct
5 Correct 507 ms 12752 KB Output is correct
6 Correct 1939 ms 9528 KB Output is correct
7 Correct 2213 ms 10388 KB Output is correct
8 Correct 2357 ms 24912 KB Output is correct
9 Correct 3633 ms 17628 KB Output is correct
10 Correct 5534 ms 33232 KB Output is correct
11 Correct 6037 ms 17352 KB Output is correct
12 Correct 1680 ms 17044 KB Output is correct
13 Correct 2469 ms 21748 KB Output is correct
14 Correct 2725 ms 22864 KB Output is correct
15 Correct 4254 ms 37588 KB Output is correct
16 Correct 4206 ms 73276 KB Output is correct
17 Correct 4037 ms 99784 KB Output is correct