oj.uz

Submission #537629

# Submission time Handle Problem Language Result Execution time Memory
537629 2022-03-15T10:15:01 Z sliviu Regions (IOI09_regions) C++17
0 / 100
 5473 ms 100752 KB 
#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;
		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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 2 ms 268 KB Output isn't correct
4 Incorrect 4 ms 208 KB Output isn't correct
5 Incorrect 7 ms 336 KB Output isn't correct
6 Incorrect 12 ms 336 KB Output isn't correct
7 Incorrect 28 ms 336 KB Output isn't correct
8 Incorrect 37 ms 464 KB Output isn't correct
9 Incorrect 61 ms 1100 KB Output isn't correct
10 Incorrect 153 ms 1128 KB Output isn't correct
11 Incorrect 290 ms 1512 KB Output isn't correct
12 Incorrect 441 ms 2264 KB Output isn't correct
13 Incorrect 678 ms 2248 KB Output isn't correct
14 Incorrect 982 ms 2676 KB Output isn't correct
15 Incorrect 1025 ms 6560 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3943 ms 7380 KB Output isn't correct
2 Incorrect 4949 ms 6760 KB Output isn't correct
3 Incorrect 5473 ms 9964 KB Output isn't correct
4 Incorrect 916 ms 2920 KB Output isn't correct
5 Incorrect 953 ms 5328 KB Output isn't correct
6 Incorrect 946 ms 27908 KB Output isn't correct
7 Incorrect 3391 ms 15212 KB Output isn't correct
8 Incorrect 3478 ms 76100 KB Output isn't correct
9 Incorrect 1222 ms 14148 KB Output isn't correct
10 Incorrect 2637 ms 100752 KB Output isn't correct
11 Incorrect 1958 ms 17096 KB Output isn't correct
12 Incorrect 950 ms 17268 KB Output isn't correct
13 Incorrect 1094 ms 18524 KB Output isn't correct
14 Incorrect 2082 ms 40396 KB Output isn't correct
15 Incorrect 1371 ms 25024 KB Output isn't correct
16 Incorrect 1616 ms 34404 KB Output isn't correct
17 Incorrect 2561 ms 54244 KB Output isn't correct