Submission #1115826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115826		vjudge1	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	226 ms	67912 KiB

catinatree

#pragma GCC optimize("Ofast" , "unroll-loops")
#include<bits/stdc++.h>

#define bit(i , j) ((j >> i) & 1)
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
using namespace std;

const int MAXN = 2e5+100;
const long long inf = 1e9 + 7;

#define int long long
#define pll pair<int , int>
#define MP make_pair

set<pll> s[MAXN];
int dep[MAXN];
vector<int> adj[MAXN];
int n , d;
void dfs(int u){
	s[u].insert({dep[u] , u});
	for(auto v : adj[u]){
		dep[v] = dep[u] + 1;
		dfs(v);
		if(s[v].size() > s[u].size()) swap(s[u] , s[v]);
		for(auto x : s[v]) s[u].insert(x);
	}

	while(s[u].size() >= 2){
		if((*s[u].begin()).fi + (*next(s[u].begin())).fi - 2 * dep[u] < d) s[u].erase(s[u].begin());
		else break;
	}
}
int32_t main(){
	//freopen("seq.inp", "r", stdin);
   //freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> d;
	for(int i = 1 ; i < n ;i ++){
		int x; cin >> x;
		adj[x].push_back(i);
	}
	dfs(0);
	cout << s[0].size() << "\n";

	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49