oj.uz

Submission #658645

# Submission time Handle Problem Language Result Execution time Memory
658645 2022-11-14T02:31:02 Z rsjw Regions (IOI09_regions) C++17
0 / 100
 64 ms 18780 KB 
#pragma GCC optimize(2)
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2 ms 3740 KB Time limit exceeded (wall clock)
2 Execution timed out 2 ms 3792 KB Time limit exceeded (wall clock)
3 Execution timed out 2 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 3792 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 3920 KB Time limit exceeded (wall clock)
8 Execution timed out 2 ms 3920 KB Time limit exceeded (wall clock)
9 Execution timed out 3 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 6 ms 4944 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 5328 KB Time limit exceeded (wall clock)
13 Execution timed out 7 ms 5556 KB Time limit exceeded (wall clock)
14 Execution timed out 11 ms 6096 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 18 ms 9424 KB Time limit exceeded (wall clock)
2 Execution timed out 20 ms 9680 KB Time limit exceeded (wall clock)
3 Execution timed out 31 ms 10528 KB Time limit exceeded (wall clock)
4 Execution timed out 9 ms 6096 KB Time limit exceeded (wall clock)
5 Execution timed out 10 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 24 ms 8988 KB Time limit exceeded (wall clock)
8 Execution timed out 23 ms 11216 KB Time limit exceeded (wall clock)
9 Execution timed out 37 ms 15024 KB Time limit exceeded (wall clock)
10 Execution timed out 40 ms 16492 KB Time limit exceeded (wall clock)
11 Execution timed out 47 ms 18780 KB Time limit exceeded (wall clock)
12 Execution timed out 48 ms 17956 KB Time limit exceeded (wall clock)
13 Execution timed out 46 ms 17992 KB Time limit exceeded (wall clock)
14 Execution timed out 64 ms 18768 KB Time limit exceeded (wall clock)
15 Execution timed out 47 ms 18716 KB Time limit exceeded (wall clock)
16 Execution timed out 58 ms 18760 KB Time limit exceeded (wall clock)
17 Execution timed out 49 ms 18700 KB Time limit exceeded (wall clock)