Submission #904292

#	Time	Username	Problem	Language	Result	Execution time	Memory
904292		IBory	Regions (IOI09_regions)	C++17	100 / 100	3327 ms	87788 KiB

regions

#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 / 15
• Subtask 2: 85 / 85