Submission #1282236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282236		Hamed_Ghaffari	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	176 ms	35820 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

const int MXN = 2e5+5, LOG = 17;

int n, d, sz[MXN];
vector<int> g[MXN];

bool dead[MXN];

int get_sz(int v, int p=-1) {
    sz[v] = 1;
    for(int u : g[v])
        if(!dead[u] && u!=p)
            sz[v] += get_sz(u, v);
    return sz[v];
}
int centroid(int v, int N, int p=-1) {
    for(int u : g[v])
        if(!dead[u] && u!=p && 2*sz[u]>N)
            return centroid(u, N, v);
    return v;
}
int h[MXN], par[MXN], dp[LOG][MXN], val[MXN];
void dfs(int id, int v, int p=-1) {
    for(int u : g[v])
        if(!dead[u] && u!=p)
            dp[id][u] = dp[id][v]+1,
            dfs(id, u, v);
}
void decompose(int v, int cur=0, int p=-1) {
    dead[v = centroid(v, get_sz(v))] = 1;
    h[v] = cur;
    par[v] = p;
    val[v] = 1e9;
    dp[h[v]][v] = 0;
    dfs(h[v], v);
    for(int u : g[v])
        if(!dead[u])
            decompose(u, cur+1, v);
}
void upd(int v) {
    for(int u=v; u!=-1; u=par[u])
        val[u] = min(val[u], dp[h[u]][v]);
}
int get(int v) {
    int res = 1e9;
    for(int u=v; u!=-1; u=par[u])
        res = min(res, dp[h[u]][v]+val[u]);
    return res;
}

int hx[MXN], ord[MXN];
void DFS(int v, int p=-1) {
    ord[v] = v;
    for(int u : g[v])
        if(u!=p)
            hx[u] = hx[v]+1,
            DFS(u, v);
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> d;
    for(int i=1; i<n; i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }
    decompose(0);
    DFS(0);
    sort(ord+1, ord+n+1, [&](int u, int v) {
        return hx[u] > hx[v];
    });
    int ans = 0;
    for(int i=1; i<=n; i++) {
        int v = ord[i];
        if(get(v)>=d) {
            ans++;
            upd(v);
        }
    }
    cout << ans << '\n';
    return 0;
}

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