Submission #1137133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137133		lucaskojima	Regions (IOI09_regions)	C++17	100 / 100	2609 ms	112420 KiB

regions

#include "bits/stdc++.h"
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const char nl = '\n';
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	int N, R, Q; cin >> N >> R >> Q;

	vector<vector<int>> adj(N + 1);
	vector<int> reg(N + 1), qnt(R + 1);

	cin >> reg[1];
	qnt[reg[1]]++;

	for (int i = 2; i <= N; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(i);
		reg[i] = b;
		qnt[b]++;
	}

	vector<int> large_id(R + 1);
	const int C = N / sqrt(Q);
	int RR = 0;

	for (int i = 1; i <= R; i++)
		if (qnt[i] > C) large_id[i] = ++RR;

	vector dp(N + 1, vector<int>(RR + 1));

	auto dfs = [&](auto dfs, int x) -> void {
		for (int k : adj[x]) {
			dfs(dfs, k);

			dp[x][large_id[reg[k]]]++;
			for (int v = 1; v <= RR; v++)
				dp[x][v] += dp[k][v];
		}
	}; dfs(dfs, 1);

	vector ans(RR + 1, vector<int>(RR + 1));

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= RR; j++)
			ans[large_id[reg[i]]][j] += dp[i][j];

	vector<vector<int>> emp(R + 1), pre(R + 1), pos(R + 1);
	vector<int> tin(N + 1), tout(N + 1);
	int tcur = 0;

	auto euler = [&](auto euler, int x) -> void {
		tin[x] = ++tcur;
		pre[reg[x]].push_back(tin[x]);
		emp[reg[x]].push_back(x);

		for (int k : adj[x])
			euler(euler, k);

		tout[x] = tcur;
		pos[reg[x]].push_back(tout[x]);
	}; euler(euler, 1);

	// tin[x] <= tin[y] <= tout[x]
	auto query_dec = [&](int i, int l, int r) -> int {
		auto ll = lower_bound(all(pre[i]), l);
		auto rr = upper_bound(all(pre[i]), r);
		return rr - ll;
	};
	auto query_anc = [&](int i, int v) -> int {
		int a = upper_bound(all(pre[i]), v) - pre[i].begin();
		int b = lower_bound(all(pos[i]), v) - pos[i].begin();
		return a - b;
	};

	map<pii, int> memo;

	while (Q--) {
		int a, b; cin >> a >> b;

		if (memo[{a, b}] != 0) {
			cout << memo[{a, b}] << endl;
			continue;
		}

		int rsp = 0;
		if (!large_id[a])
			for (int x : emp[a])
				rsp += query_dec(b, tin[x], tout[x]);
		else if (!large_id[b])
			for (int y : emp[b])
				rsp += query_anc(a, tin[y]);
		else
			rsp = ans[large_id[a]][large_id[b]];

		memo[{a, b}] = rsp;
		cout << rsp << endl;
	}
	return 0;
}

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