제출 #1137118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137118		lucaskojima	Regions (IOI09_regions)	C++17	70 / 100	8087 ms	103232 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> r(N + 1);

	for (int i = 1; i <= N; i++) {
		if (i == 1) {
			int a; cin >> a;
			r[i] = a;
		} else {
			int a, b; cin >> a >> b;
			adj[a].push_back(i);
			adj[i].push_back(a);
			r[i] = b;
		}
	}

	auto subtask1 = [&]() -> void { // O(NR + Q)
		vector dp(N + 1, vector<int>(R + 1));

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

				dp[x][r[k]]++;
				for (int v = 1; v <= R; v++)
					dp[x][v] += dp[k][v];
			}
		}; dfs(dfs, 1, -1);

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

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= R; j++)
				ans[r[i]][j] += dp[i][j];

		while (Q--) {
			int a, b; cin >> a >> b;
			cout << ans[a][b] << endl;
		}
	};

	auto subtask2 = [&]() -> void { // O(N + Q(S1 + S1)log(S1 + S2))
		vector<vector<int>> emp(R + 1);
		vector<int> tin(N + 1), tout(N + 1);
		int tcur = 0;

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

			for (int k : adj[x]) {
				if (k == p) continue;
				euler(euler, k, x);
			}
			tout[x] = tcur;
		}; euler(euler, 1, -1);

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

			vector<pii> line;
			for (int x : emp[a]) {
				line.push_back({tin[x], 1});
				line.push_back({tout[x], 3});
			}
			for (int y : emp[b])
				line.push_back({tin[y], 2});

			sort(all(line));

			int ans = 0, cnt = 0;
			for (auto [d, t] : line) {
				if (t == 1) cnt++;
				if (t == 2) ans += cnt;
				if (t == 3) cnt--;
			}

			cout << ans << endl;
		}
	};

	if (R <= 500) subtask1();
	else subtask2();
	return 0;
}

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