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

regions

#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;
		}
	}
}

Subtask #1

15.0 / 15.0

#	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

Subtask #2

85.0 / 85.0

#	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