Submission #1099568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099568		ASN49K	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	280 ms	239192 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
mt19937 rng(69);


namespace lmao
{
    int main(int n,int dist,vector<int>&p)
    {
        vector<deque<int>>dp(n);
        for(auto &c:dp)
        {
            c.push_back(1);
        }
        for(int i=n-1;i>0;i--)
        {
            dp[i].push_front(dp[i].front());
            if((int)dp[i].size()==dist+2)
            {
                dp[i].pop_back();
            }
            deque<int>&b=dp[i],&a=dp[p[i]];
            if(a.size()<b.size())
            {
                swap(a,b);
            }
            map<int,int>new_dp;
            for(int i=b.size()-1;i>=0;i--)
            {
                int remain=dist-i;
                int val=b[i];
                if(remain<(int)a.size())
                {
                    if(a[remain]==a[i])
                    {
                        remain=max(remain,i);
                    }
                    val+=a[remain];
                }
                new_dp[min(i,remain)]=max(new_dp[min(i,remain)] , val);
            }
            for(int i=(int)b.size()-1;i>=0;i--)
            {
                a[i]=max(a[i] , b[i]);
            }
            for(auto &c:new_dp)
            {
                a[c.first]=max(a[c.first] , c.second);
            }
            for(int i=(int)b.size()-2;i>=0;i--)
            {
                a[i]=max(a[i],a[i+1]);
            }
        }
        return dp[0][0];
    }
}

namespace good
{
    int main(int n,int dist,vector<int>&p)
    {
        vector<int>h(n);
        for(int i=1;i<n;i++)
        {
            h[i]=h[p[i]]+1;
        }

        auto get_dist=[&](int x,int y)->int
        {
            if(h[x]<h[y])
            {
                swap(x,y);
            }

            int rez=0;
            while(h[x]>h[y])
            {
                x=p[x];
                rez++;
            }
            while(x!=y)
            {
                rez+=2;
                x=p[x];
                y=p[y];
            }
            return rez;
        };

        int sol=0;
        for(int i=1;i<(1<<n);i++)
        {
            vector<int>poz;
            for(int j=0;j<n;j++)
            {
                if((i>>j)&1)
                {
                    poz.pb(j);
                }
            }
            bool ok=true;
            int k=(int)poz.size();
            for(int i=0;i<k;i++)
            {
                for(int j=0;j<i;j++)
                {
                    if(get_dist(poz[i],poz[j]) < dist)
                    {
                        ok=false;
                    }
                }
            }
            if(ok)
            {
                sol=max(sol , k);
            }
        }
        return sol;
    }
};
main()
{
    int n,dist;
    cin>>n>>dist;
    vector<int>p(n,0);
    for(int i=1;i<n;i++)
    {
        cin>>p[i];
    }
    cout<<lmao::main(n,dist,p);

    /*const int n=15;
    while(true)
    {
        const int dist=rng()%n+1;
        vector<int>p(n);
        for(int i=1;i<n;i++)
        {
            p[i]=rng()%i;
        }

        if(good::main(n,dist,p)!=lmao::main(n,dist,p))
        {
            cout<<n<<' '<<dist<<'\n';
            for(int i=1;i<n;i++)
            {
                cout<<p[i]<<'\n';
            }
            break;
        }
    }*/
}

Compilation message (stderr)

catinatree.cpp:128:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  128 | main()
      | ^~~~

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