Submission #366643

#	Time	Username	Problem	Language	Result	Execution time	Memory
366643		penguinhacker	Regions (IOI09_regions)	C++14	100 / 100	4230 ms	89700 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"

template<class T> ostream& operator<< (ostream& out, vector<T>& v) {
	out << '[';
	for (int i = 0; i < v.size(); ++i) {
		if (i > 0) {
			out << ", ";
		}
		out << v[i];
	}
	return out << ']';
}

const int mxN = 200000;
const int B = 200; // change this
int n, m, q, reg[mxN], p[mxN], tin[mxN], tout[mxN], timer = 0, dp[mxN + 1], r[mxN];
vector<int> adj[mxN], oc[mxN], pos[mxN];
vector<int> pre[mxN];

void dfs(int u = 0) {
	tin[u] = timer++;
	pos[reg[u]].push_back(tin[u]);
	for (int v : adj[u]) dfs(v);
	tout[u] = timer - 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < n; ++i) {
		if (i > 0) {
			cin >> p[i], --p[i];
			adj[p[i]].push_back(i);
		}
		cin >> reg[i], --reg[i];
	}
	dfs();
	for (int i = 0; i < n; ++i) {
		r[tin[i]] = i;
		oc[reg[i]].push_back(i);
	}
	for (int i = 0; i < m; ++i) if (oc[i].size() > B) {
		pre[i].resize(m);
		for (int u : oc[i]) {
			++dp[tin[u]];
			--dp[tout[u] + 1];
		}
		for (int j = 1; j < n; ++j) dp[j] += dp[j - 1];
		for (int j = 0; j < n; ++j) pre[i][reg[r[j]]] += dp[j];
		pre[i][i] -= oc[i].size();
		//debug(pre[i]);
		memset(dp, 0, 4 * n);
	}
	for (int i = 0; i < q; ++i) {
		int a, b; cin >> a >> b, --a, --b;
		if (oc[a].size() > B) {
			cout << pre[a][b] << endl;
			continue;
		}
		int ans = 0;
		for (int u : oc[a]) {
			ans += upper_bound(pos[b].begin(), pos[b].end(), tout[u]) - lower_bound(pos[b].begin(), pos[b].end(), tin[u]);
		}
		cout << ans << endl;
	}
	return 0;
}

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