oj.uz

Submission #537631

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 3 ms 208 KB Output isn't correct
4 Incorrect 5 ms 208 KB Output isn't correct
5 Incorrect 7 ms 336 KB Output isn't correct
6 Incorrect 20 ms 336 KB Output isn't correct
7 Incorrect 28 ms 336 KB Output isn't correct
8 Incorrect 32 ms 464 KB Output isn't correct
9 Incorrect 70 ms 1100 KB Output isn't correct
10 Incorrect 166 ms 1132 KB Output isn't correct
11 Incorrect 266 ms 1512 KB Output isn't correct
12 Incorrect 388 ms 2256 KB Output isn't correct
13 Incorrect 646 ms 2216 KB Output isn't correct
14 Incorrect 976 ms 2676 KB Output isn't correct
15 Incorrect 987 ms 6560 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 3794 ms 7336 KB Output isn't correct
2 Incorrect 4960 ms 6808 KB Output isn't correct
3 Incorrect 5396 ms 9988 KB Output isn't correct
4 Incorrect 912 ms 2932 KB Output isn't correct
5 Incorrect 952 ms 5320 KB Output isn't correct
6 Incorrect 909 ms 27716 KB Output isn't correct
7 Incorrect 3499 ms 15204 KB Output isn't correct
8 Incorrect 3751 ms 76072 KB Output isn't correct
9 Incorrect 1225 ms 14196 KB Output isn't correct
10 Incorrect 2759 ms 100852 KB Output isn't correct
11 Incorrect 1983 ms 17196 KB Output isn't correct
12 Incorrect 958 ms 17368 KB Output isn't correct
13 Incorrect 1086 ms 18452 KB Output isn't correct
14 Incorrect 1968 ms 40416 KB Output isn't correct
15 Incorrect 1820 ms 24988 KB Output isn't correct
16 Incorrect 1543 ms 34508 KB Output isn't correct
17 Incorrect 2079 ms 54232 KB Output isn't correct