oj.uz

답안 #537645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537645 2022-03-15T10:38:19 Z sliviu Regions (IOI09_regions) C++17
100 / 100
 4762 ms 101700 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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