Submission #658642

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
658642	2022-11-14T01:58:30 Z	rsjw	Regions (IOI09_regions)	C++17	0 / 100	88 ms	49640 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	15 ms	33164 KB	Time limit exceeded (wall clock)
2	Execution timed out	14 ms	33104 KB	Time limit exceeded (wall clock)
3	Execution timed out	15 ms	33104 KB	Time limit exceeded (wall clock)
4	Execution timed out	17 ms	33116 KB	Time limit exceeded (wall clock)
5	Execution timed out	14 ms	33232 KB	Time limit exceeded (wall clock)
6	Execution timed out	14 ms	33360 KB	Time limit exceeded (wall clock)
7	Execution timed out	15 ms	33232 KB	Time limit exceeded (wall clock)
8	Execution timed out	16 ms	33360 KB	Time limit exceeded (wall clock)
9	Execution timed out	16 ms	33616 KB	Time limit exceeded (wall clock)
10	Execution timed out	17 ms	34000 KB	Time limit exceeded (wall clock)
11	Execution timed out	18 ms	34384 KB	Time limit exceeded (wall clock)
12	Execution timed out	21 ms	34788 KB	Time limit exceeded (wall clock)
13	Execution timed out	20 ms	35104 KB	Time limit exceeded (wall clock)
14	Execution timed out	23 ms	35596 KB	Time limit exceeded (wall clock)
15	Execution timed out	24 ms	36432 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	39 ms	39056 KB	Time limit exceeded (wall clock)
2	Execution timed out	32 ms	39528 KB	Time limit exceeded (wall clock)
3	Execution timed out	43 ms	40256 KB	Time limit exceeded (wall clock)
4	Execution timed out	23 ms	35656 KB	Time limit exceeded (wall clock)
5	Execution timed out	24 ms	36176 KB	Time limit exceeded (wall clock)
6	Execution timed out	29 ms	37412 KB	Time limit exceeded (wall clock)
7	Execution timed out	41 ms	38928 KB	Time limit exceeded (wall clock)
8	Execution timed out	41 ms	41344 KB	Time limit exceeded (wall clock)
9	Execution timed out	53 ms	45576 KB	Time limit exceeded (wall clock)
10	Execution timed out	67 ms	47300 KB	Time limit exceeded (wall clock)
11	Execution timed out	77 ms	49640 KB	Time limit exceeded (wall clock)
12	Execution timed out	64 ms	48580 KB	Time limit exceeded (wall clock)
13	Execution timed out	66 ms	48536 KB	Time limit exceeded (wall clock)
14	Execution timed out	88 ms	49448 KB	Time limit exceeded (wall clock)
15	Execution timed out	69 ms	49612 KB	Time limit exceeded (wall clock)
16	Execution timed out	72 ms	49592 KB	Time limit exceeded (wall clock)
17	Execution timed out	73 ms	49460 KB	Time limit exceeded (wall clock)