Submission #631058

#	Time	Username	Problem	Language	Result	Execution time	Memory
631058		Dorost	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	567 ms	172952 KiB

catinatree

/* In the name of GOD */
 
#include <bits/stdc++.h>

#define S second
#define F first
using namespace std;
const int N = 200000, K = 205;
vector <int> g[N];
int h[N];
bool is[N];
int dp[N][K];
int s[K];
int n, d;
int t = 0;

void dfs(int v, int p = -1) {
    if (h[v] < d)
        is[v] = false;
    for (int u : g[v]) 
        if (u != p) {
            h[u] = h[v] + 1;
            dfs(u, v); 
        }
}

void dfs2(int v, int p = -1) {
    for (int u : g[v]) 
        if (u != p) {
            dfs2(u, v); 
        }
    for (int i = 0; i < K; i++)
        s[i] = 0;
    for (int u : g[v]) 
        if (u != p)  
            for (int i = 0; i < K; i++)
                s[i] += dp[u][i];
    for (int i = K - 1; i >= 1; i--) {
        if (i != K - 1)  
            dp[v][i] = dp[v][i + 1]; 
        for (int u : g[v]) 
            if (u != p) {
                int h = i - 1;
                dp[v][i] = max(dp[v][i], s[max(d - h - 2, h)] - dp[u][max(d - h - 2, h)] + dp[u][h]);
            }
    }   
    dp[v][0] = max(dp[v][1], 1 + dp[v][d]);
}

int32_t main() {
    cin >> n >> d;
    if (d <= 1) {
        cout << n << '\n';
        return 0;
    }   
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }   
    if (d < K) {
        dfs2(0);
        cout << dp[0][0] << '\n';
        return 0;
    }   
    int ans = 0;
    vector <pair <int, int>> v;
    dfs(0);
    for (int i = 0; i < n; i++)
        is[i] = true;
    for (int i = 0; i < n; i++) {
        v.push_back(make_pair(h[i], i));
    }   
    sort(v.begin(), v.end());
    while (!v.empty()) {
        pair <int, int> p = v.back();
        v.pop_back();
        if (is[p.S]) {
            t++;
            ans++;
            h[p.S] = 0;
            dfs(p.S);
        }
    }   
    cout << ans << '\n';
}

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