Submission #1115827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115827		flyingkite	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	193 ms	126444 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 1e3;
ll n,d;
vector<ll>adj[N];
ll dep[N];
set<pll>s[N];
void dfs(ll u, ll par){
    s[u].insert({dep[u], u});
    for(auto v : adj[u]){
        if(v == par) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        if(s[u].size() < s[v].size()) swap(s[u], s[v]);
        for(auto x : s[v]) s[u].insert(x);
    }
    while(s[u].size() >= 2){
        auto it = s[u].begin();
        ll d1 = (*it).F; ++it; ll d2 = (*it).F;
        if(d1 + d2 - 2 * dep[u] < d) s[u].erase(s[u].begin());
        else break;
    }
}
void to_thic_cau(){
    cin >> n >> d;
    for(int i = 2; i <= n;i++){
        ll p; cin >> p; p++;
        adj[p].pb(i);
    }
    dfs(1, 0);
    cout << s[1].size() << "\n";
}

signed main()
{   
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1;   
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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