Submission #1115906

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

catinatree

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define read_input(file) if (fopen(file".inp", "r")) freopen(file".inp", "r", stdin);
#define file(file) freopen (file".inp", "r", stdin); freopen (file".out", "w", stdout);

const int N = 2e5;
int n, k, mx[N + 5], h[N + 5];
vector <int> g[N + 5];
set <pair <int,int>> v[N + 5];

void dfs(int i){
	v[i].insert({h[i], i});
	for (int j : g[i]){
		h[j] = h[i] + 1;
		dfs(j);
		if (v[i].size() < v[j].size()) swap(v[i], v[j]);
		for (pair <int,int> p : v[j]) v[i].insert(p);
	}
	while (v[i].size() >= 2){
		if ((*v[i].begin()).fi + (*next(v[i].begin())).fi - 2 * h[i] < k) v[i].erase(v[i].begin());
		else break;
	}
}

void solve(){
	cin >> n >> k;
	for (int i = 1; i < n; ++i){
		int p;
		cin >> p;
		g[p].push_back(i);
	}
	dfs(0);
	cout << v[0].size();
}

signed main(){
    faster;
    // file("file");
    // read_input("file");
    int tt = 1;
    // cin >> tt;
    while (tt--){
        solve();
    }
}

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