oj.uz

Submission #730349

# Submission time Handle Problem Language Result Execution time Memory
730349 2023-04-25T17:48:44 Z NintsiChkhaidze Regions (IOI09_regions) C++17
85 / 100
 6950 ms 131072 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
using namespace std;

const int N = 2e5+5,Bl=505;

vector <int> v[N],st[25005],ynull;
int r[N],tin[N],tout[N],cnt[25005],timer,id[25005];
int fen[N],B,k[25005][Bl],DP[Bl][25005];
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]++;
		for (int i=0;i<B;i++)
			DP[i+1][r[x]] += Pnew[i];
	}

	for (int to: v[x])
		if (to != par) {
			vector <int> 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[r[x]][i + 1] += vec[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]; cnt[r[1]]++; st[r[1]].pb(1);
	for(int i=2;i<=n;i++){
		int p;
		cin>>p>>r[i];
		cnt[r[i]]++; st[r[i]].pb(i);
		v[p].pb(i);
		v[i].pb(p);
	}
	
	B = 0;
	for (int i = 1; i <= R; i++){
		if (cnt[i] > Bl){
			++B;
			id[i] = B; 
			big[i] = 1; 
		}
	}
	
	for (int i=0;i<B;i++) ynull.pb(0);
	dfs(1,1,ynull);
	while (q--){
		int r1,r2,ans=0;
		cin>>r1>>r2;

		if (!big[r1] && !big[r2]){
			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[r1][id[r2]]<<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 7 ms 5712 KB Output is correct
3 Correct 5 ms 5584 KB Output is correct
4 Correct 6 ms 5632 KB Output is correct
5 Correct 10 ms 5712 KB Output is correct
6 Correct 26 ms 5844 KB Output is correct
7 Correct 31 ms 5732 KB Output is correct
8 Correct 39 ms 5840 KB Output is correct
9 Correct 63 ms 6864 KB Output is correct
10 Correct 106 ms 6352 KB Output is correct
11 Correct 139 ms 6864 KB Output is correct
12 Correct 123 ms 7908 KB Output is correct
13 Correct 228 ms 7504 KB Output is correct
14 Correct 285 ms 8016 KB Output is correct
15 Correct 400 ms 15548 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1748 ms 19456 KB Output is correct
2 Correct 1976 ms 13820 KB Output is correct
3 Correct 3403 ms 29100 KB Output is correct
4 Correct 384 ms 8272 KB Output is correct
5 Correct 471 ms 12752 KB Output is correct
6 Correct 1499 ms 10576 KB Output is correct
7 Correct 2538 ms 11956 KB Output is correct
8 Correct 2348 ms 24788 KB Output is correct
9 Correct 3756 ms 20492 KB Output is correct
10 Correct 6524 ms 33960 KB Output is correct
11 Correct 6950 ms 22396 KB Output is correct
12 Correct 1834 ms 76768 KB Output is correct
13 Correct 2650 ms 81176 KB Output is correct
14 Correct 2465 ms 94408 KB Output is correct
15 Runtime error 157 ms 131072 KB Execution killed with signal 9
16 Runtime error 127 ms 131072 KB Execution killed with signal 9
17 Runtime error 125 ms 131072 KB Execution killed with signal 9