Submission #537631

#	Time	Username	Problem	Language	Result	Execution time	Memory
537631		sliviu	Regions (IOI09_regions)	C++17	0 / 100	5396 ms	100852 KiB

regions

#include <bits/stdc++.h>

using namespace std;

int main() {
	const int SQRT = 450;
	int n, r, q, x, y, t = -1;
	cin >> n >> r >> q;
	vector<vector<int>> G(n + 1), regnodes(r + 1);
	vector<int> tin(n + 1), tout(n + 1), reg(n + 1), nodes;
	cin >> reg[1];
	for (int i = 2; i <= n; ++i) {
		cin >> x >> reg[i];
		G[x].emplace_back(i);
		G[i].emplace_back(x);
	}
	function<void(int, int)> dfs = [&](int node, int last) {
		tin[node] = ++t;
		regnodes[reg[node]].emplace_back(t);
		nodes.emplace_back(node);
		for (auto x : G[node])
			if (x != last)
				dfs(x, node);
		tout[node] = t;
	};
	dfs(1, 0);
	map<pair<int, int>, int> ans;
	for (int i = 1; i <= n; ++i)
		if (regnodes[i].size() >= SQRT) {
			for (int j = 0; j <= t;)
				if (reg[nodes[j]] == i) {
					int end = tout[nodes[j]];
					for (++j; j <= end; ++j)
						++ans[{i, reg[nodes[j]]}];
				}
				else
					++j;
		}
	while (q--) {
		cin >> x >> y;
		assert(x != y);
		if (regnodes[x].size() >= SQRT)
			cout << ans[{x, y}] << endl;
		else {
			int ans = 0, last = -1;
			for (auto x : regnodes[x])
				if (x > last) {
					ans += upper_bound(regnodes[y].begin(), regnodes[y].end(), tout[nodes[x]]) - lower_bound(regnodes[y].begin(), regnodes[y].end(), x);
					last = tout[nodes[x]];
				}
			cout << ans << endl;
		}
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85