Submission #537645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
537645	2022-03-15T10:38:19 Z	sliviu	Regions (IOI09_regions)	C++17	100 / 100	4762 ms	101700 KB

regions

#include <bits/stdc++.h>

using namespace std;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	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 <= r; ++i)
		if (regnodes[i].size() >= SQRT) {
			vector<int> cur(t + 2);
			for (auto x : regnodes[i])
				++cur[x], --cur[tout[nodes[x]] + 1];
			for (int j = 1; j <= t; ++j) {
				cur[j] += cur[j - 1];
				ans[{i, reg[nodes[j]]}] += cur[j];
			}
		}
	while (q--) {
		cin >> x >> y;
		if (regnodes[x].size() >= SQRT)
			cout << ans[{x, y}] << endl;
		else {
			int ans = 0;
			for (auto x : regnodes[x])
				ans += upper_bound(regnodes[y].begin(), regnodes[y].end(), tout[nodes[x]]) - lower_bound(regnodes[y].begin(), regnodes[y].end(), x);
			cout << ans << endl;
		}
	}
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	2 ms	208 KB	Output is correct
4	Correct	5 ms	208 KB	Output is correct
5	Correct	6 ms	336 KB	Output is correct
6	Correct	15 ms	336 KB	Output is correct
7	Correct	22 ms	336 KB	Output is correct
8	Correct	34 ms	464 KB	Output is correct
9	Correct	44 ms	1104 KB	Output is correct
10	Correct	72 ms	1104 KB	Output is correct
11	Correct	123 ms	1488 KB	Output is correct
12	Correct	94 ms	2304 KB	Output is correct
13	Correct	163 ms	2256 KB	Output is correct
14	Correct	254 ms	2704 KB	Output is correct
15	Correct	266 ms	6468 KB	Output is correct

Subtask #2

85.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1848 ms	7532 KB	Output is correct
2	Correct	1872 ms	7024 KB	Output is correct
3	Correct	2568 ms	10336 KB	Output is correct
4	Correct	231 ms	2948 KB	Output is correct
5	Correct	340 ms	5488 KB	Output is correct
6	Correct	813 ms	28336 KB	Output is correct
7	Correct	1708 ms	15492 KB	Output is correct
8	Correct	2287 ms	76604 KB	Output is correct
9	Correct	2076 ms	14264 KB	Output is correct
10	Correct	4762 ms	101700 KB	Output is correct
11	Correct	3623 ms	17144 KB	Output is correct
12	Correct	1261 ms	18016 KB	Output is correct
13	Correct	2091 ms	19244 KB	Output is correct
14	Correct	2732 ms	41132 KB	Output is correct
15	Correct	3441 ms	25816 KB	Output is correct
16	Correct	2839 ms	35140 KB	Output is correct
17	Correct	3354 ms	54876 KB	Output is correct