Submission #1106298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1106298	2024-10-29T18:38:32 Z	ssitaram	Regions (IOI09_regions)	C++17	100 / 100	3715 ms	44872 KB

regions

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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