Submission #658643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658643	2022-11-14T02:02:42 Z	rsjw	Regions (IOI09_regions)	C++17	0 / 100	63 ms	18764 KB

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) {
	s[h[u]]++;
	for (auto x : _top[h[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]]) {
		if (s1.find(x) != s1.end())
			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]]++;
	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);
		}
	}
	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.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2 ms	3792 KB	Time limit exceeded (wall clock)
2	Execution timed out	2 ms	3792 KB	Time limit exceeded (wall clock)
3	Execution timed out	3 ms	3792 KB	Time limit exceeded (wall clock)
4	Execution timed out	2 ms	3792 KB	Time limit exceeded (wall clock)
5	Execution timed out	2 ms	3792 KB	Time limit exceeded (wall clock)
6	Execution timed out	2 ms	3920 KB	Time limit exceeded (wall clock)
7	Execution timed out	3 ms	3920 KB	Time limit exceeded (wall clock)
8	Execution timed out	3 ms	3920 KB	Time limit exceeded (wall clock)
9	Execution timed out	4 ms	4176 KB	Time limit exceeded (wall clock)
10	Execution timed out	4 ms	4560 KB	Time limit exceeded (wall clock)
11	Execution timed out	7 ms	4880 KB	Time limit exceeded (wall clock)
12	Execution timed out	8 ms	5328 KB	Time limit exceeded (wall clock)
13	Execution timed out	9 ms	5612 KB	Time limit exceeded (wall clock)
14	Execution timed out	11 ms	5968 KB	Time limit exceeded (wall clock)
15	Execution timed out	10 ms	6736 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	17 ms	9424 KB	Time limit exceeded (wall clock)
2	Execution timed out	18 ms	9808 KB	Time limit exceeded (wall clock)
3	Execution timed out	20 ms	10444 KB	Time limit exceeded (wall clock)
4	Execution timed out	7 ms	6096 KB	Time limit exceeded (wall clock)
5	Execution timed out	9 ms	6608 KB	Time limit exceeded (wall clock)
6	Execution timed out	13 ms	7632 KB	Time limit exceeded (wall clock)
7	Execution timed out	16 ms	9040 KB	Time limit exceeded (wall clock)
8	Execution timed out	22 ms	11216 KB	Time limit exceeded (wall clock)
9	Execution timed out	37 ms	14964 KB	Time limit exceeded (wall clock)
10	Execution timed out	37 ms	16456 KB	Time limit exceeded (wall clock)
11	Execution timed out	55 ms	18720 KB	Time limit exceeded (wall clock)
12	Execution timed out	49 ms	18016 KB	Time limit exceeded (wall clock)
13	Execution timed out	63 ms	17996 KB	Time limit exceeded (wall clock)
14	Execution timed out	47 ms	18764 KB	Time limit exceeded (wall clock)
15	Execution timed out	47 ms	18760 KB	Time limit exceeded (wall clock)
16	Execution timed out	44 ms	18760 KB	Time limit exceeded (wall clock)
17	Execution timed out	47 ms	18760 KB	Time limit exceeded (wall clock)