oj.uz

Submission #870887

# Submission time Handle Problem Language Result Execution time Memory
870887 2023-11-09T11:49:58 Z rsjw Regions (IOI09_regions) C++17
0 / 100
 46 ms 19824 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 1 ms 4948 KB Time limit exceeded (wall clock)
2 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
4 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
5 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
6 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
7 Execution timed out 2 ms 4696 KB Time limit exceeded (wall clock)
8 Execution timed out 1 ms 4696 KB Time limit exceeded (wall clock)
9 Execution timed out 2 ms 4952 KB Time limit exceeded (wall clock)
10 Execution timed out 3 ms 5464 KB Time limit exceeded (wall clock)
11 Execution timed out 4 ms 5720 KB Time limit exceeded (wall clock)
12 Execution timed out 7 ms 5976 KB Time limit exceeded (wall clock)
13 Execution timed out 5 ms 6492 KB Time limit exceeded (wall clock)
14 Execution timed out 6 ms 6764 KB Time limit exceeded (wall clock)
15 Execution timed out 7 ms 7532 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 15 ms 10256 KB Time limit exceeded (wall clock)
2 Execution timed out 14 ms 10532 KB Time limit exceeded (wall clock)
3 Execution timed out 18 ms 11380 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 6744 KB Time limit exceeded (wall clock)
5 Execution timed out 8 ms 7256 KB Time limit exceeded (wall clock)
6 Execution timed out 10 ms 8488 KB Time limit exceeded (wall clock)
7 Execution timed out 15 ms 9800 KB Time limit exceeded (wall clock)
8 Execution timed out 18 ms 12224 KB Time limit exceeded (wall clock)
9 Execution timed out 37 ms 15816 KB Time limit exceeded (wall clock)
10 Execution timed out 31 ms 17420 KB Time limit exceeded (wall clock)
11 Execution timed out 40 ms 19716 KB Time limit exceeded (wall clock)
12 Execution timed out 39 ms 18736 KB Time limit exceeded (wall clock)
13 Execution timed out 35 ms 18808 KB Time limit exceeded (wall clock)
14 Execution timed out 46 ms 19692 KB Time limit exceeded (wall clock)
15 Execution timed out 37 ms 19712 KB Time limit exceeded (wall clock)
16 Execution timed out 45 ms 19824 KB Time limit exceeded (wall clock)
17 Execution timed out 46 ms 19540 KB Time limit exceeded (wall clock)