oj.uz

Submission #658644

# Submission time Handle Problem Language Result Execution time Memory
658644 2022-11-14T02:26:38 Z rsjw Regions (IOI09_regions) C++17
0 / 100
 50 ms 18788 KB 
#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 3 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 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 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 5 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 9 ms 5584 KB Time limit exceeded (wall clock)
14 Execution timed out 8 ms 5968 KB Time limit exceeded (wall clock)
15 Execution timed out 14 ms 6736 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 19 ms 9424 KB Time limit exceeded (wall clock)
2 Execution timed out 19 ms 9808 KB Time limit exceeded (wall clock)
3 Execution timed out 21 ms 10448 KB Time limit exceeded (wall clock)
4 Execution timed out 10 ms 6096 KB Time limit exceeded (wall clock)
5 Execution timed out 14 ms 6544 KB Time limit exceeded (wall clock)
6 Execution timed out 13 ms 7632 KB Time limit exceeded (wall clock)
7 Execution timed out 17 ms 9040 KB Time limit exceeded (wall clock)
8 Execution timed out 24 ms 11196 KB Time limit exceeded (wall clock)
9 Execution timed out 36 ms 14976 KB Time limit exceeded (wall clock)
10 Execution timed out 40 ms 16520 KB Time limit exceeded (wall clock)
11 Execution timed out 47 ms 18760 KB Time limit exceeded (wall clock)
12 Execution timed out 46 ms 17996 KB Time limit exceeded (wall clock)
13 Execution timed out 44 ms 17984 KB Time limit exceeded (wall clock)
14 Execution timed out 45 ms 18716 KB Time limit exceeded (wall clock)
15 Execution timed out 45 ms 18752 KB Time limit exceeded (wall clock)
16 Execution timed out 50 ms 18788 KB Time limit exceeded (wall clock)
17 Execution timed out 45 ms 18784 KB Time limit exceeded (wall clock)