Submission #1106298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106298		ssitaram	Regions (IOI09_regions)	C++17	100 / 100	3715 ms	44872 KiB

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 (stderr)

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 / 15
• Subtask 2: 85 / 85