Submission #348574

#	Time	Username	Problem	Language	Result	Execution time	Memory
348574		Nima_Naderi	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	240 ms	25312 KiB

catinatree

///In the name of GOD
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e5 + 10;
ll n, m, ans;
ll h[MXN], dis[MXN];
vector<ll> adj[MXN], Ver;
void DFS(ll u, ll par, ll d){
    if(d >= m || d >= dis[u]) return;
    dis[u] = d;
    for(auto v : adj[u]){
        if(v != par) DFS(v, u, d + 1);
    }
}
void dfs(ll u, ll par){
    Ver.push_back(u);
    for(auto v : adj[u]){
        if(v != par){
            h[v] = h[u] + 1;
            dfs(v, u);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    memset(dis, 63, sizeof dis);
    cin >> n >> m;
    for(int i = 2; i <= n; i ++){
        ll x; cin >> x, x ++;
        adj[i].push_back(x), adj[x].push_back(i);
    }
    dfs(1, 0);
    sort(Ver.begin(), Ver.end(), [&](const int& u, const int &v){
        return h[u] > h[v];
    });
    for(auto u : Ver){
        if(dis[u] < m) continue;
        ans ++;
        DFS(u, 0, 0);
    }
    cout << ans << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

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