제출 #1306478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306478		BigBadBully	Cat in a tree (BOI17_catinatree)	C++20	51 / 100	1097 ms	51060 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int inf = 2e9;
const int mod = 1e9 + 7;
const int mxn = 2e5 + 1;

int exp(int x, int n)
{
    int res = 1;
    for (; n > 0; res = (n % 2 ? res * x % mod : res), x = x * x % mod, n /= 2)
        ;
    return res;
}

int inv(int x)
{
    return exp(x, mod - 2);
}

struct seggy {
    int n;
    vector<int> tree;
    seggy(int sz)
    {
        n = sz;
        tree.resize(2*n);
    }
    int query(int l,int r)
    {
        r++;
        int res = 0;
        for(l+=n,r+=n;l<r;l/=2,r/=2)
        {
            if(l&1)
                res+=tree[l++];
            if(r&1)
                res+=tree[--r];
        }
        return res;
    }
    void update(int i,int x)
    {
        for(tree[i+=n]=x;i>1;i/=2)
            tree[i/2]=tree[i]+tree[i^1];
    }
    int query(int i)
    {
        return query(0,i);
    }
    void update(int l,int r,int x)
    {
        update(l,x);
        if(r<n-1)
            update(r+1,-x);
    }
};

void solve()
{
    int n, d;
    cin >> n >> d;
    
    vector<vector<int>> g(n);
    for (int i = 1; i < n; i++)
    {
        int x;
        cin >> x;
        g[i].push_back(x);
        g[x].push_back(i);
    }
    vector<int> depth(n, -1),p(n);
    vector<vector<int>> lift(20,vector<int>(n));
    
    function<int(int,int)> lca = [&](int a,int b)
    {
        if(depth[a]<depth[b])swap(a,b);
        int raz = depth[a]-depth[b];
        for(int bit = 19;bit >= 0;bit--)
            if(raz&(1<<bit))
                a = lift[bit][a];

        for(int bit = 19;bit >= 0;bit--)
            if(lift[bit][a]!=lift[bit][b])
                a = lift[bit][a],b= lift[bit][b];

        if(a!=b)
            a = p[a];
        return a;            
    };
    function<int(int,int)> dist=  [&](int a,int b)
    {
        return depth[a]+depth[b]-2*depth[lca(a,b)];
    };
    function<void(int, int)> dfs = [&](int cur, int prev)
    {
        depth[cur] = depth[prev] + 1;
        for (int a : g[cur])
            if (a != prev)
                dfs(a, cur);
        p[cur] = prev;
    };
    dfs(0, 0);
    lift[0] = p;
    for(int b = 1;b < 20;b++)
        for(int i = 0; i <n; i++)
            lift[b][i] = lift[b-1][lift[b-1][i]];
    vector<vector<int>> anc(n);
    vector<int> rem(n,0);
    vector<int> sbt(n);
    function<int(int,int)> getsz = [&](int cur,int prev)
    {
        sbt[cur] = 1;
        for(int  a: g[cur])
            if(a!=prev && !rem[a])
                sbt[cur]+=getsz(a,cur);
        return sbt[cur];
    };
    function<int(int,int,int)> centroid = [&](int cur,int trsz,int prev)
    {
        
        for(int a : g[cur])
            if(a!=prev && !rem[a])
                if(sbt[a]*2>trsz)
                    return centroid(a,trsz,cur);
        return cur;
    };
    function<void(int)> decomp = [&](int cur)
    {
        int c = centroid(cur,getsz(cur,cur),cur);
        rem[c] = 1;
        function<void(int,int)> doanc = [&](int cur,int prev)
        {
            anc[cur].push_back(c);
            for(int a: g[cur])
                if(a!=prev&&!rem[a])
                    doanc(a,cur);
        };
        doanc(c,c);
        for(int a : g[c])
            if(!rem[a])
            decomp(a);
    };
    decomp(0);
    int cnt = 0;
    vector<int> vis(n, 0);
    vector<int> id(n);
    vector<int> mini(n,inf);
    for (int i = 0; i < n; i++)
        id[i] = i;
    sort(id.begin(), id.end(), [&](int a, int b)
         { return depth[a] > depth[b]; });
    for (int i : id)
    {
        bool stop = 0;
        for(int a : anc[i])
            if(!stop && mini[a]+dist(a,i) < d)
                stop = 1;
        if(stop)continue;
        cnt++;
        for(int a : anc[i])
            mini[a] = min(mini[a],dist(a,i));
    }
    cout << cnt << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >>t;
    while (t--)
        solve();
    return 0;
}

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