Submission #689610

# Submission time Handle Problem Language Result Execution time Memory
689610 2023-01-28T20:41:35 Z bane Regions (IOI09_regions) C++17
100 / 100
4187 ms 35552 KB
#include <bits/stdc++.h>
using namespace std;
#define siz(x) (int)x.size()
#define pb push_back
#define all(x) x.begin(), x.end()
const int MAX = 2e5+5;
const int BLOCK = 500;
vector<int> adj[MAX], comp[MAX], occ[MAX];
int cmp[MAX], in[MAX], sub[MAX], res[400][25005], pp[MAX], curr;

int dfs(int v){
	in[v] = ++curr;
	occ[cmp[v]].pb(in[v]);
	for (int u: adj[v]) sub[v] += dfs(u);
	return (sub[v] += 1);
}

void dfs2(int v, int tar, int curr){
	if (cmp[v] == tar) curr++;
	res[pp[tar]][cmp[v]] += curr;
	for (int u: adj[v]) dfs2(u, tar, curr);
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, r, q; cin >> n >> r >> q;
	for (int i = 1; i <= n; i++){
		if (i > 1){
			int a; cin >> a;
			adj[a].pb(i);
		}
		cin >> cmp[i];
		comp[cmp[i]].pb(i);
	}
	dfs(1);
	curr = 0;
	for (int i = 1; i <= r; i++){
		if (siz(comp[i]) < BLOCK) continue;
		pp[i] = ++curr;
		dfs2(1, i, 0);
	}
	while (q--){
		int a, b; cin >> a >> b;
		if (pp[a]) cout << res[pp[a]][b] << endl;
		else {
			int tot = 0;
			for (int v: comp[a])
				tot += lower_bound(all(occ[b]), in[v]+sub[v])-lower_bound(all(occ[b]), in[v]);
			cout << tot << endl;
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 14416 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 9 ms 14416 KB Output is correct
4 Correct 11 ms 14328 KB Output is correct
5 Correct 15 ms 14416 KB Output is correct
6 Correct 25 ms 14416 KB Output is correct
7 Correct 28 ms 14416 KB Output is correct
8 Correct 34 ms 14544 KB Output is correct
9 Correct 44 ms 14928 KB Output is correct
10 Correct 76 ms 14888 KB Output is correct
11 Correct 73 ms 15184 KB Output is correct
12 Correct 151 ms 15648 KB Output is correct
13 Correct 192 ms 15352 KB Output is correct
14 Correct 273 ms 16040 KB Output is correct
15 Correct 265 ms 18512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1494 ms 19116 KB Output is correct
2 Correct 1974 ms 17968 KB Output is correct
3 Correct 2890 ms 20844 KB Output is correct
4 Correct 195 ms 16092 KB Output is correct
5 Correct 359 ms 17616 KB Output is correct
6 Correct 1113 ms 17836 KB Output is correct
7 Correct 1700 ms 18376 KB Output is correct
8 Correct 1355 ms 23400 KB Output is correct
9 Correct 2391 ms 23792 KB Output is correct
10 Correct 4048 ms 28744 KB Output is correct
11 Correct 4187 ms 23716 KB Output is correct
12 Correct 1366 ms 25232 KB Output is correct
13 Correct 1969 ms 25428 KB Output is correct
14 Correct 2317 ms 27008 KB Output is correct
15 Correct 3169 ms 29724 KB Output is correct
16 Correct 2248 ms 34888 KB Output is correct
17 Correct 2416 ms 35552 KB Output is correct