oj.uz

Submission #730332

# Submission time Handle Problem Language Result Execution time Memory
730332 2023-04-25T17:33:42 Z NintsiChkhaidze Regions (IOI09_regions) C++17
50 / 100
 2116 ms 99068 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;

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

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

	if (x != 1){
		for (int i = 1; i <= B; i++)
			DP[i][x] += DP[i][par];
		if (big[r[par]])
			DP[id[r[par]]][x]++;
	}

	for (int to: v[x])
		if (to != par) {
			vector <int> o = dfs(to,x);
			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; 
		}
	}

	dfs(1,1);
	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{
			for (int x: st[r2])
				ans += DP[id[r1]][x];
			cout<<ans<<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 8 ms 5584 KB Output is correct
5 Correct 7 ms 5584 KB Output is correct
6 Correct 24 ms 5712 KB Output is correct
7 Correct 35 ms 5712 KB Output is correct
8 Correct 29 ms 5712 KB Output is correct
9 Correct 50 ms 6480 KB Output is correct
10 Correct 101 ms 6172 KB Output is correct
11 Correct 127 ms 6480 KB Output is correct
12 Correct 141 ms 7120 KB Output is correct
13 Correct 233 ms 6964 KB Output is correct
14 Correct 357 ms 9568 KB Output is correct
15 Correct 250 ms 53496 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 19220 KB Execution killed with signal 11
2 Correct 944 ms 63800 KB Output is correct
3 Runtime error 35 ms 20428 KB Execution killed with signal 11
4 Correct 356 ms 11800 KB Output is correct
5 Correct 439 ms 10320 KB Output is correct
6 Correct 492 ms 27368 KB Output is correct
7 Correct 898 ms 39096 KB Output is correct
8 Correct 1046 ms 99068 KB Output is correct
9 Correct 2116 ms 93772 KB Output is correct
10 Runtime error 66 ms 28616 KB Execution killed with signal 11
11 Runtime error 82 ms 31572 KB Execution killed with signal 11
12 Runtime error 81 ms 29388 KB Execution killed with signal 11
13 Runtime error 70 ms 29512 KB Execution killed with signal 11
14 Runtime error 78 ms 30624 KB Execution killed with signal 11
15 Runtime error 73 ms 30968 KB Execution killed with signal 11
16 Runtime error 102 ms 30808 KB Execution killed with signal 11
17 Runtime error 74 ms 30664 KB Execution killed with signal 11