Submission #658644

#	Time	Username	Problem	Language	Result	Execution time	Memory
658644		rsjw	Regions (IOI09_regions)	C++17	0 / 100	50 ms	18788 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const int R = 25005;
int h[N];
int threshold;
struct edge {
	int to;
	edge *nex;
} * head[N];
void add(int u, int v) {
	edge *cur = new edge;
	cur->to = v;
	cur->nex = head[u];
	head[u] = cur;
}
struct query {
	int a, b;
} q[N];
int cnt[R];
vector<int> _sub[R], _top[R];
map<int, int> sub[R], top[R];
map<int, int> s;
void dfs1(int u, int fa) {

	for (auto x : _top[h[u]])
		top[h[u]][x] += s[x];
	s[h[u]]++;
	for (edge *cur = head[u]; cur; cur = cur->nex) {
		if (cur->to == fa)
			continue;
		dfs1(cur->to, u);
	}
	if (s[h[u]] == 1)
		s.erase(h[u]);
	else
		s[h[u]]--;
}
map<int, int> dfs2(int u, int fa) {
	map<int, int> s1, s2;
	for (edge *cur = head[u]; cur; cur = cur->nex) {
		if (cur->to == fa)
			continue;
		s2 = dfs2(cur->to, u);
		if (s2.size() > s1.size())
			swap(s1, s2);
		for (auto x : s2)
			s1[x.first] += x.second;
	}
	for (auto x : _sub[h[u]]) {
		if (s1.find(x) != s1.end())
			sub[h[u]][x] += s1[x];
	}
	s1[h[u]]++;
	return s1;
}
void get() {
	int n, m, t, i, x;
	cin >> n >> m >> t >> h[1];
	cnt[h[1]]++;
	for (i = 2; i <= n; i++) {
		cin >> x >> h[i];
		cnt[h[i]]++;
		add(x, i);
		add(i, x);
	}
	threshold = sqrt(n);
	for (i = 1; i <= t; i++) {
		cin >> q[i].a >> q[i].b;
		if (cnt[q[i].b] >= threshold) {
			_sub[q[i].a].push_back(q[i].b);
		} else {
			_top[q[i].b].push_back(q[i].a);
		}
	}
	for (i = 1; i <= m; i++) {
		sort(_sub[i].begin(), _sub[i].end());
		_sub[i].erase(unique(_sub[i].begin(), _sub[i].end()), _sub[i].end());
		sort(_top[i].begin(), _top[i].end());
		_top[i].erase(unique(_top[i].begin(), _top[i].end()), _top[i].end());
	}
	dfs1(1, 0);
	dfs2(1, 0);
	for (i = 1; i <= t; i++) {
		if (cnt[q[i].b] >= threshold) {
			cout << sub[q[i].a][q[i].b] << endl;
		} else {
			cout << top[q[i].b][q[i].a] << endl;
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	get();
	return 0;
}

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