oj.uz

답안 #658642

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658642 2022-11-14T01:58:30 Z rsjw Regions (IOI09_regions) C++17
0 / 100
 88 ms 49640 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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)