Submission #1306477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306477		BigBadBully	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	874 ms	67956 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);
}


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(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: 49 / 49