Submission #1231431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231431		wedonttalkanymore	Regions (IOI09_regions)	C++20	100 / 100	2405 ms	49260 KiB

regions

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define pii pair <ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 500;

int n, r, q;
int h[N], in[N], out[N], cnt, temp[N];
vector <int> adj[N];
vector <pii> pre[N];
vector <int> heavy[N];

void predfs(int u, int par) {
	in[u] = ++cnt;
	for (auto v : adj[u]) {
		if (v != par) {
			predfs(v, u);
		}
	}
	out[u] = cnt;
	pre[h[u]].emplace_back(in[u], out[u]);
}

void dfs(int u, int par, int sum, int target) {
	if (h[u] == target) sum++;
	temp[h[u]] += sum;
	for (auto v : adj[u]) {
		if (v != par) {
			dfs(v, u, sum, target);
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> r >> q >> h[1];
	for (int i = 2; i <= n; i++) {
		int u;
		cin >> u >> h[i];
		adj[u].push_back(i);
	}
	predfs(1, 0);
	for (int i = 1; i <= r; i++) {
		sort(pre[i].begin(), pre[i].end());
	}
	while(q-- > 0) {
		int r1, r2;
		cin >> r1 >> r2;
		if (pre[r1].size() < block) {
			int ans = 0;
			for (auto x : pre[r1]) {
				auto it1 = lower_bound(pre[r2].begin(), pre[r2].end(), make_pair(x.fi, 0LL)) - pre[r2].begin();
				auto it2 = upper_bound(pre[r2].begin(), pre[r2].end(), make_pair(x.se, inf)) - pre[r2].begin();
				ans += it2 - it1;
			}
			cout << ans << '\n' << flush;
		}
		else {
			if (heavy[r1].empty()) {
				for (int i = 1; i <= r; i++) {
					temp[i] = 0;
				}
				dfs(1, 0, 0, r1);
				heavy[r1].resize(r + 1, 0);
				for (int i = 1; i <= r; i++) {
					heavy[r1][i] = temp[i];
				}
			}
			cout << heavy[r1][r2] << '\n' << flush;
		}
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85