Submission #1129888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129888		vladilius	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	532 ms	589824 KiB

catinatree

#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";
}

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