제출 #1129888

#제출 시각아이디문제언어결과실행 시간메모리
1129888vladiliusCat in a tree (BOI17_catinatree)C++20
51 / 100
532 ms589824 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, D; cin>>n>>D;
    vector<int> g[n + 1];
    for (int i = 2; i <= n; i++){
        int p; cin>>p; p++;
        g[p].pb(i);
        g[i].pb(p);
    }

    vector<vector<int>> dist(n + 1, vector<int>(n + 1));
    function<void(int, int, int&)> dfs = [&](int v, int pr, int& k){
        for (int i: g[v]){
            if (i == pr) continue;
            dist[k][i] = dist[k][v] + 1;
            dfs(i, v, k);
        }
    };
    
    for (int i = 1; i <= n; i++) dfs(i, 0, i);
    
    vector<int> d(n + 1);
    function<void(int, int)> fill = [&](int v, int pr){
        for (int i: g[v]){
            if (i == pr) continue;
            d[i] = d[v] + 1;
            fill(i, v);
        }
    };
    fill(1, 0);
    
    vector<int> all;
    for (int i = 1; i <= n; i++) all.pb(i);
    
    int out = 0;
    while (!all.empty()){
        out++;
        pii mx = {-1, 0};
        for (int i: all){
            mx = max(mx, {d[i], i});
        }
        vector<int> nw;
        for (int i: all){
            if (dist[mx.ss][i] >= D){
                nw.pb(i);
            }
        }
        all = nw;
    }
    
    cout<<out<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...