oj.uz

답안 #1106298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106298 2024-10-29T18:38:32 Z ssitaram Regions (IOI09_regions) C++17
100 / 100
 3715 ms 44872 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, r, q; cin >> n >> r >> q;
	vector<int> h(n);
	vector<vector<int>> chldr(n);
	cin >> h[0];
	for (int i = 1; i < n; ++i) {
		int p; cin >> p >> h[i];
		chldr[--p].push_back(i);
	}
	vector<vector<int>> nodesinr(r);
	for (int i = 0; i < n; ++i) {
		nodesinr[--h[i]].push_back(i);
	}
	vector<vector<ll>> answers(r);
	for (int i = 0; i < r; ++i) {
		if ((ll) nodesinr[i].size() * nodesinr[i].size() < n) continue;
		answers[i].resize(r);
		int c = 0;
		function<void(int)> dfs;
		dfs = [&](int node) -> void {
			answers[i][h[node]] += c;
			if (h[node] == i) ++c;
			for (int j : chldr[node]) {
				dfs(j);
			}
			if (h[node] == i) --c;
		};
		dfs(0);
	}
	vector<int> in(n), ot(n);
	vector<vector<int>> nodesinrt(n);
	function<void(int)> dfs;
	int t = 0;
	dfs = [&](int node) -> void {
		in[node] = t++;
		nodesinrt[h[node]].push_back(in[node]);
		for (int i : chldr[node]) {
			dfs(i);
		}
		ot[node] = t;
	};
	dfs(0);
	while (q--) {
		int r1, r2; cin >> r1 >> r2;
		--r1; --r2;
		if (answers[r1].size() != 0) {
			cout << answers[r1][r2] << endl;
			continue;
		}
		ll ans = 0;
		for (int i : nodesinr[r1]) {
			int i1 = upper_bound(nodesinrt[r2].begin(), nodesinrt[r2].end(), in[i]) - nodesinrt[r2].begin();
			int i2 = lower_bound(nodesinrt[r2].begin(), nodesinrt[r2].end(), ot[i]) - nodesinrt[r2].begin();
			ans += i2 - i1;
		}
		cout << ans << endl;
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:23:52: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'int' [-Wsign-compare]
   23 |   if ((ll) nodesinr[i].size() * nodesinr[i].size() < n) continue;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 3 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 13 ms 592 KB Output is correct
7 Correct 22 ms 592 KB Output is correct
8 Correct 23 ms 592 KB Output is correct
9 Correct 27 ms 1104 KB Output is correct
10 Correct 57 ms 1608 KB Output is correct
11 Correct 93 ms 2020 KB Output is correct
12 Correct 110 ms 2816 KB Output is correct
13 Correct 157 ms 2620 KB Output is correct
14 Correct 225 ms 3408 KB Output is correct
15 Correct 218 ms 7140 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1623 ms 8912 KB Output is correct
2 Correct 1909 ms 7772 KB Output is correct
3 Correct 2602 ms 11716 KB Output is correct
4 Correct 220 ms 3768 KB Output is correct
5 Correct 307 ms 6112 KB Output is correct
6 Correct 563 ms 9528 KB Output is correct
7 Correct 1082 ms 12360 KB Output is correct
8 Correct 1014 ms 23476 KB Output is correct
9 Correct 2143 ms 17736 KB Output is correct
10 Correct 2722 ms 44872 KB Output is correct
11 Correct 3715 ms 20396 KB Output is correct
12 Correct 1237 ms 21100 KB Output is correct
13 Correct 1706 ms 21556 KB Output is correct
14 Correct 2094 ms 25168 KB Output is correct
15 Correct 2847 ms 27616 KB Output is correct
16 Correct 2814 ms 34704 KB Output is correct
17 Correct 2636 ms 36264 KB Output is correct