Submission #1367813

#TimeUsernameProblemLanguageResultExecution timeMemory
1367813maya_sCat in a tree (BOI17_catinatree)C++20
51 / 100
228 ms589824 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
typedef long long ll;
const ll SIZE = 200200;
vector<ll> g[SIZE];

ll dfs(ll node, ll d, ll &cnt){
    vector<ll> v(g[node].size());
    for(ll i = 0; i < g[node].size(); i++) v[i] = dfs(g[node][i], d, cnt);
    sort(v.begin(), v.end());
    while(v.size() && v.back() == d) v.pop_back();
    if(v.empty()) {cnt++; return 1;}
    reverse(v.begin(), v.end());
    while(v.size() > 1 && v[v.size()-1] + v[v.size()-2] < d) cnt--, v.pop_back();
    return v.back() + 1;
}

ll solve(ll n, ll k){
    if(k >= n) return 1;
    vector<vector<ll>> dp(n, vector<ll>(k+2));
    ll cnt = 0;
    dfs(0, k, cnt);
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, k; cin >> n >> k;
    for(ll i = 1; i <= n-1; i++){
        ll p; cin >> p;
        g[p].push_back(i);
    }
    cout << solve(n, k);
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...