oj.uz

Submission #904292

# Submission time Handle Problem Language Result Execution time Memory
904292 2024-01-12T02:36:20 Z IBory Regions (IOI09_regions) C++17
100 / 100
 3327 ms 87788 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 200007, CUT = 500;
vector<int> G[MAX], R[MAX], P[25005];
int C[MAX], in[MAX], out[MAX], cnt[MAX], dn;

void DFS(int cur) {
	in[cur] = ++dn;
	for (int next : G[cur]) DFS(next);
	out[cur] = dn;
}

void DFS2(int cur, int col, int d) {
	if (C[cur] == col) d++;
	else cnt[C[cur]] += d;
	for (int next : G[cur]) DFS2(next, col, d);
}

int Process(int a, int b) {
	int ret = 0;
	for (int n : R[a]) ret += upper_bound(P[b].begin(), P[b].end(), out[n]) - lower_bound(P[b].begin(), P[b].end(), in[n]);
	return ret;
}

int main() {
	int N, M, Q;
	cin >> N >> M >> Q;
	cin >> C[1];
	R[C[1]].push_back(1);
	for (int i = 2; i <= N; ++i) {
		int p;
		cin >> p >> C[i];
		R[C[i]].push_back(i);
		G[p].push_back(i);
	}

	DFS(1);
	for (int i = 1; i <= N; ++i) P[C[i]].push_back(in[i]);
	for (int i = 1; i <= M; ++i) sort(P[i].begin(), P[i].end());

	map<pii, int> pre;
	vector<int> big;
	for (int i = 1; i <= M; ++i) if (R[i].size() > CUT) big.push_back(i);

	for (int b : big) {
		for (int a = 1; a <= M; ++a) {
			if (a == b) continue;
			pre[{a, b}] = Process(a, b);
		}
	}

	for (int a : big) {
		memset(cnt, 0, sizeof(cnt));
		DFS2(1, a, 0);
		for (int b = 1; b <= M; ++b) {
			if (a == b) continue;
			pre[{a, b}] = cnt[b];
		}
	}

	while (Q--) {
		int a, b, ans = -1;
		cin >> a >> b;
		if (pre.find({a, b}) != pre.end()) ans = pre[{a, b}];
		else ans = Process(a, b);
		cout << ans << '\n';
		cout.flush();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 4 ms 13144 KB Output is correct
3 Correct 4 ms 13284 KB Output is correct
4 Correct 5 ms 13144 KB Output is correct
5 Correct 7 ms 13400 KB Output is correct
6 Correct 12 ms 13400 KB Output is correct
7 Correct 17 ms 13400 KB Output is correct
8 Correct 18 ms 13400 KB Output is correct
9 Correct 32 ms 13656 KB Output is correct
10 Correct 48 ms 13656 KB Output is correct
11 Correct 87 ms 13960 KB Output is correct
12 Correct 102 ms 14244 KB Output is correct
13 Correct 123 ms 13908 KB Output is correct
14 Correct 209 ms 14604 KB Output is correct
15 Correct 209 ms 16064 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 17316 KB Output is correct
2 Correct 1118 ms 16124 KB Output is correct
3 Correct 1795 ms 19076 KB Output is correct
4 Correct 183 ms 14644 KB Output is correct
5 Correct 243 ms 15656 KB Output is correct
6 Correct 1093 ms 15384 KB Output is correct
7 Correct 1303 ms 16376 KB Output is correct
8 Correct 938 ms 19544 KB Output is correct
9 Correct 1753 ms 20664 KB Output is correct
10 Correct 3327 ms 23836 KB Output is correct
11 Correct 3180 ms 20144 KB Output is correct
12 Correct 1122 ms 25872 KB Output is correct
13 Correct 1576 ms 25936 KB Output is correct
14 Correct 2622 ms 76900 KB Output is correct
15 Correct 2626 ms 32432 KB Output is correct
16 Correct 2395 ms 38308 KB Output is correct
17 Correct 2971 ms 87788 KB Output is correct