oj.uz

Submission #941969

# Submission time Handle Problem Language Result Execution time Memory
941969 2024-03-09T21:00:52 Z andrei_c1 Cat in a tree (BOI17_catinatree) C++17
51 / 100
 12 ms 11160 KB 
#include <bits/stdc++.h>
using namespace std;

const int kN = 1e5;
const int kLog = 19;
const int kInf = 1e9;

int dep[kN], tin[kN];
vector<int> adj[kN], rmq[kLog];

void dfs(int u) {
	tin[u] = rmq[0].size();
	rmq[0].emplace_back(u);
	for(const auto &v: adj[u]) {
		dfs(v);
		rmq[0].emplace_back(u);
	}
}

int minNode(int u, int v) {
	if(dep[u] < dep[v]) return u;
	return v;
}

int lca(int u, int v) {
	int l = tin[u], r = tin[v];
	if(l > r) swap(l, r);
	int lg = __lg(r - l + 1);
	return minNode(rmq[lg][l], rmq[lg][r - (1 << lg) + 1]);
}

int dist(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void minSelf(int &x, int y) {
	if(y < x) {
		x = y;
	}
}

int findClosest(int u, const vector<int> &nodes) {
	int res = kInf;
	for(const auto &v: nodes) {
		minSelf(res, dist(u, v));
	}
	return res;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, d;
	cin >> n >> d;
	for(int i = 1; i < n; i++) {
		int x;
		cin >> x;
		adj[x].emplace_back(i);
		dep[i] = dep[x] + 1;
	}
	rmq[0].reserve(2 * n);
	dfs(0);
	for(int i = 1; (1 << i) < 2 * n; i++) {
		for(int j = 0; j + (1 << i) - 1 < 2 * n - 1; j++) {
			rmq[i].emplace_back(minNode(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
		}
	}
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&] (int u, int v) {
		return dep[u] > dep[v];
	});
	vector<int> nodes;
	for(const auto &u: ord) {
		int closest = findClosest(u, nodes);
		if(closest >= d) {
			nodes.emplace_back(u);
		}
	}
	cout << nodes.size() << '\n';
	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2820 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2820 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2908 KB Output is correct
22 Correct 2 ms 2812 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 5 ms 2908 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 1 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 3 ms 3048 KB Output is correct
30 Correct 1 ms 2908 KB Output is correct
31 Correct 1 ms 2908 KB Output is correct
32 Correct 1 ms 2908 KB Output is correct
33 Correct 1 ms 3060 KB Output is correct
34 Correct 1 ms 2908 KB Output is correct
35 Correct 1 ms 2908 KB Output is correct
36 Correct 1 ms 2904 KB Output is correct
37 Correct 1 ms 2908 KB Output is correct
38 Correct 1 ms 2908 KB Output is correct
39 Correct 1 ms 2904 KB Output is correct
40 Correct 3 ms 2908 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2820 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2652 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2652 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2908 KB Output is correct
22 Correct 2 ms 2812 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 5 ms 2908 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 1 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 3 ms 3048 KB Output is correct
30 Correct 1 ms 2908 KB Output is correct
31 Correct 1 ms 2908 KB Output is correct
32 Correct 1 ms 2908 KB Output is correct
33 Correct 1 ms 3060 KB Output is correct
34 Correct 1 ms 2908 KB Output is correct
35 Correct 1 ms 2908 KB Output is correct
36 Correct 1 ms 2904 KB Output is correct
37 Correct 1 ms 2908 KB Output is correct
38 Correct 1 ms 2908 KB Output is correct
39 Correct 1 ms 2904 KB Output is correct
40 Correct 3 ms 2908 KB Output is correct
41 Runtime error 12 ms 11160 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -