Submission #700107

#	Time	Username	Problem	Language	Result	Execution time	Memory
700107		tamthegod	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	492 ms	85660 KiB

catinatree

// Make the best become better
// No room for laziness
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, d;
vector<int> adj[maxN];
int depth[maxN];
int id[maxN];
int sz[maxN], vis[maxN];
int parCent[maxN];
int f[maxN][20];
void ReadInput()
{
    cin >> n >> d;
    for(int i=2; i<=n; i++)
    {
        int p;
        cin >> p;
        p++;
        adj[p].pb(i);
        adj[i].pb(p);
    }
}
void predfs(int u, int par)
{
    for(int v : adj[u])
    {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        f[v][0] = u;
        for(int i=1; i<=18; i++)
            f[v][i] = f[f[v][i - 1]][i - 1];
        predfs(v, u);
    }
}
int dfs(int u, int par)
{
    sz[u] = 1;
    for(int v : adj[u])
    {
        if(vis[v] || v == par) continue;
        sz[u] += dfs(v, u);
    }
    return sz[u];
}
int Find_Centroid(int u, int par, int _sz)
{
    for(int v : adj[u])
    {
        if(v == par || vis[v]) continue;
        if(sz[v] > _sz / 2) return Find_Centroid(v, u, _sz);
    }
    return u;
}
int Decompose(int u)
{
    int root = Find_Centroid(u, 0, dfs(u, 0));
    vis[root] = -1;
    for(int v : adj[root])
    {
        if(vis[v]) continue;
        parCent[Decompose(v)] = root;
    }
    return root;
}
int lca(int u, int v)
{
    if(depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    for(int i=18; i>=0; i--)
        if((k >> i) & 1)
            u = f[u][i];
    if(u == v) return u;
    for(int i=18; i>=0; i--)
        if(f[u][i] != f[v][i])
        {
            u = f[u][i];
            v = f[v][i];
        }
    return f[u][0];
}
int dist(int u, int v)
{
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
int dp[maxN];
void upd(int u)
{
    for(int v=u; v; v=parCent[v])
        dp[v] = min(dp[v], dist(u, v));
}
int get(int u)
{
    int res = oo;
    for(int v=u; v; v=parCent[v])
        res = min(res, dist(u, v) + dp[v]);
    return res;
}
void Solve()
{
    memset(dp, 3, sizeof dp);
    predfs(1, 0);
    iota(id + 1, id + n + 1, 1);
    sort(id + 1, id + n + 1, [](int i, int j)
    {
        return depth[i] > depth[j];
    });
    int res = 0;
    Decompose(1);
    for(int i=1; i<=n; i++)
    {
        int j = id[i];
        if(get(j) >= d)
        {
            res++;
            upd(j);
        }
    }
    cout << res;
}
int32_t main()
{
    //freopen("sol.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

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