oj.uz

답안 #658641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658641 2022-11-14T01:57:47 Z rsjw Regions (IOI09_regions) C++17
0 / 100
 3 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
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 1 ms 208 KB Time limit exceeded (wall clock)
2 Execution timed out 0 ms 208 KB Time limit exceeded (wall clock)
3 Execution timed out 1 ms 208 KB Time limit exceeded (wall clock)
4 Runtime error 1 ms 464 KB Execution killed with signal 11
5 Runtime error 1 ms 464 KB Execution killed with signal 11
6 Runtime error 1 ms 464 KB Execution killed with signal 11
7 Runtime error 1 ms 464 KB Execution killed with signal 11
8 Runtime error 2 ms 464 KB Execution killed with signal 11
9 Runtime error 2 ms 464 KB Execution killed with signal 11
10 Runtime error 1 ms 464 KB Execution killed with signal 11
11 Runtime error 3 ms 592 KB Execution killed with signal 6
12 Runtime error 1 ms 464 KB Execution killed with signal 11
13 Runtime error 1 ms 464 KB Execution killed with signal 11
14 Runtime error 2 ms 464 KB Execution killed with signal 11
15 Runtime error 1 ms 464 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 464 KB Execution killed with signal 11
2 Runtime error 2 ms 572 KB Execution killed with signal 6
3 Runtime error 1 ms 464 KB Execution killed with signal 11
4 Runtime error 1 ms 464 KB Execution killed with signal 11
5 Runtime error 1 ms 336 KB Execution killed with signal 11
6 Runtime error 1 ms 436 KB Execution killed with signal 11
7 Runtime error 1 ms 464 KB Execution killed with signal 11
8 Runtime error 1 ms 464 KB Execution killed with signal 11
9 Runtime error 1 ms 464 KB Execution killed with signal 11
10 Runtime error 1 ms 464 KB Execution killed with signal 11
11 Runtime error 2 ms 464 KB Execution killed with signal 11
12 Runtime error 1 ms 464 KB Execution killed with signal 11
13 Runtime error 1 ms 464 KB Execution killed with signal 11
14 Runtime error 1 ms 464 KB Execution killed with signal 11
15 Runtime error 1 ms 464 KB Execution killed with signal 11
16 Runtime error 1 ms 464 KB Execution killed with signal 11
17 Runtime error 1 ms 336 KB Execution killed with signal 11