oj.uz

Submission #917665

# Submission time Handle Problem Language Result Execution time Memory
917665 2024-01-28T14:25:04 Z dsyz Cat in a tree (BOI17_catinatree) C++17
51 / 100
 1000 ms 18892 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (200005)
ll N,D;
vector<ll> v[MAXN];
bool cannot[MAXN];
vector<pair<ll,ll> > sortbydepth;
void dfs1(ll x,ll p,ll level){
	sortbydepth.push_back({level,x});
	for(auto u : v[x]){
		if(u != p){
			dfs1(u,x,level + 1);
		}	
	}
}
void dfs2(ll x,ll p,ll distance){
	cannot[x] = true;
	for(auto u : v[x]){
		if(u != p && distance + 1 < D){
			dfs2(u,x,distance + 1);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N>>D;
	for(ll i = 1;i < N;i++){
		ll p;
		cin>>p;
		v[p].push_back(i);
		v[i].push_back(p);
	}
	dfs1(0,-1,-1);
	sort(sortbydepth.begin(),sortbydepth.end(),greater<pair<ll,ll> >());
	ll ans = 0;
	for(auto u : sortbydepth){
		ll x = u.second;
		if(cannot[x]) continue; //node x is within dist D from a node selected so far so we can greedily prove that it is not optimal to delete the selected node (with greater depth) and replace it with node x (with lower depth)
		ans++;
		dfs2(x,-1,0); //mark the nodes within D distance as cannot be picked
	}
	cout<<ans<<'\n';
}

Subtask #1
11.0 / 11.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5000 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5184 KB Output is correct
5 Correct 2 ms 5184 KB Output is correct
6 Correct 1 ms 5004 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 1 ms 4956 KB Output is correct
18 Correct 1 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 2 ms 5212 KB Output is correct
23 Correct 2 ms 5220 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Correct 2 ms 5212 KB Output is correct
29 Correct 2 ms 5184 KB Output is correct
30 Correct 2 ms 5212 KB Output is correct
31 Correct 2 ms 5212 KB Output is correct
32 Correct 2 ms 5212 KB Output is correct
33 Correct 2 ms 5212 KB Output is correct
34 Correct 2 ms 5212 KB Output is correct
35 Correct 2 ms 5212 KB Output is correct
36 Correct 2 ms 5212 KB Output is correct
37 Correct 2 ms 5212 KB Output is correct
38 Correct 2 ms 5464 KB Output is correct
39 Correct 2 ms 5212 KB Output is correct
40 Correct 2 ms 5212 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 5000 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 5184 KB Output is correct
5 Correct 2 ms 5184 KB Output is correct
6 Correct 1 ms 5004 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 2 ms 4956 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 1 ms 4956 KB Output is correct
14 Correct 1 ms 4956 KB Output is correct
15 Correct 1 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 1 ms 4956 KB Output is correct
18 Correct 1 ms 4956 KB Output is correct
19 Correct 2 ms 4956 KB Output is correct
20 Correct 2 ms 4956 KB Output is correct
21 Correct 2 ms 5212 KB Output is correct
22 Correct 2 ms 5212 KB Output is correct
23 Correct 2 ms 5220 KB Output is correct
24 Correct 2 ms 5212 KB Output is correct
25 Correct 2 ms 5212 KB Output is correct
26 Correct 2 ms 5212 KB Output is correct
27 Correct 2 ms 5212 KB Output is correct
28 Correct 2 ms 5212 KB Output is correct
29 Correct 2 ms 5184 KB Output is correct
30 Correct 2 ms 5212 KB Output is correct
31 Correct 2 ms 5212 KB Output is correct
32 Correct 2 ms 5212 KB Output is correct
33 Correct 2 ms 5212 KB Output is correct
34 Correct 2 ms 5212 KB Output is correct
35 Correct 2 ms 5212 KB Output is correct
36 Correct 2 ms 5212 KB Output is correct
37 Correct 2 ms 5212 KB Output is correct
38 Correct 2 ms 5464 KB Output is correct
39 Correct 2 ms 5212 KB Output is correct
40 Correct 2 ms 5212 KB Output is correct
41 Execution timed out 1049 ms 18892 KB Time limit exceeded
42 Halted 0 ms 0 KB -