Submission #658642

#	Time	Username	Problem	Language	Result	Execution time	Memory
658642		rsjw	Regions (IOI09_regions)	C++17	0 / 100	88 ms	49640 KiB

regions

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
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[N];
vector<int> _sub[N], _top[N];
map<int, int> sub[N], top[N];
vector<int> pt[N];
map<int, int> s;
void dfs1(int u, int fa) {
	s[h[u]]++;
	for (auto x : _top[u])
		top[h[u]][x] += s[x];
	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;
	}
	s1[h[u]]++;
	for (auto x : _sub[h[u]])
		sub[h[u]][x] += s1[x];
	return s1;
}
void get() {
	int n, m, t, i, x;
	cin >> n >> m >> t >> h[1];
	cnt[h[1]]++;
	pt[h[1]].push_back(1);
	for (i = 2; i <= n; i++) {
		cin >> x >> h[i];
		pt[h[i]].push_back(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);
		}
	}
	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