Submission #372770

#	Time	Username	Problem	Language	Result	Execution time	Memory
372770		ngpin04	Regions (IOI09_regions)	C++14	100 / 100	5022 ms	64484 KiB

regions

 #include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int S = 700;

map <int, int> ans[N];

vector <int> adj[N];
vector <int> id[N];

int grp[N];
int tin[N];
int tout[N];
int sum[N];
int n,m,q,cntdfs;

void dfs(int u = 1) {
	tin[u] = ++cntdfs;
	for (int v : adj[u]) 
		dfs(v);
	tout[u] = cntdfs;
}

void calc(int idgrp) {
	memset(sum, 0, sizeof(sum));

	for (int i : id[idgrp]) 
		sum[tin[i]]++, sum[tout[i] + 1]--;

	for (int i = 1; i <= n; i++)
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n; i++) 
		if (grp[i] != idgrp) 
			ans[idgrp][grp[i]] += sum[tin[i]];

	memset(sum, 0, sizeof(sum));

	for (int i : id[idgrp]) 
		sum[tin[i]]++;

	for (int i = 1; i <= n; i++) 
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n; i++)
		if (grp[i] != idgrp) 
			ans[grp[i]][idgrp] += sum[tout[i]] - sum[tin[i] - 1]; 
}

int solve(int u, int v) {
	int res = 0;
	vector <int> a;
	for (int i : id[v]) 
		a.push_back(tin[i]);
	
	for (int i : id[u]) 
		res += upper_bound(a.begin(), a.end(), tout[i]) - lower_bound(a.begin(), a.end(), tin[i]);

	return res;
}

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

	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {	
		if (i > 1) {
			int p; cin >> p;
			adj[p].push_back(i);
		}
		cin >> grp[i];
		id[grp[i]].push_back(i);
	}
	dfs();

	for (int i = 1; i <= m; i++)
		sort(id[i].begin(), id[i].end(), [](int i, int j) {return tin[i] < tin[j];});

	for (int i = 1; i <= m; i++) 
		if (id[i].size() > S) 
			calc(i);

	for (int i = 1; i <= m; i++) if (id[i].size() > S) {
		for (int j = 1; j <= m; j++) if (id[j].size() > S) 
			ans[i][j] /= 2;
	}

	while (q--) {
		int u,v;
		cin >> u >> v;
		if (id[u].size() > S || id[v].size() > S) 
			cout << ans[u][v] << endl;
		else 
			cout << solve(u, v) << endl;
	}
	return 0;
}

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