Submission #444593

#	Time	Username	Problem	Language	Result	Execution time	Memory
444593		leaked	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	638 ms	156356 KiB

catinatree

#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;
struct segtree{
    vec<int>t,l,r,p;
//    void clr
    segtree(){
        t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);
    }
    void clr(){
        t.clear();l.clear();r.clear();p.clear();
    }
    void checkl(int v){
        if(l[v]==-1){t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);l[v]=sz(t)-1;}
    }
    void checkr(int v){
        if(r[v]==-1){t.pb(0);l.pb(-1);r.pb(-1);p.pb(0);r[v]=sz(t)-1;}
    }
    void push(int v,int tl,int tr){
        if(tl==tr || p[v]==0) return;
        checkl(v);checkr(v);
        t[l[v]]+=p[v];t[r[v]]+=p[v];
        p[l[v]]+=p[v];p[r[v]]+=p[v];
        p[v]=0;
    }
    void pull(int v){
        t[v]=max((l[v]==-1?0:t[l[v]]),(r[v]==-1?0:t[r[v]]));
    }
    void upd(int id,int x,int v,int tl,int tr){
        if(tl==tr){
            umax(t[v],x);
//            cerr<<"HEY "<<t[v]<<endl;
            return;
        }
        int tm=(tl+tr)>>1;push(v,tl,tr);
        if(tm>=id){
            checkl(v);
            upd(id,x,l[v],tl,tm);
        }
        else{
            checkr(v);
            upd(id,x,r[v],tm+1,tr);
        }
        pull(v);
//        cerr<<"HEY"<<' '<<v<<' '<<t[v]<<endl;
    }
    void add(int l1,int r1,int x,int v,int tl,int tr){
        if(tl>=l1 && tr<=r1){
            t[v]+=x;p[v]+=x;
            return;
        }
        if(tl>r1 || tr<l1) return;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        checkl(v);checkr(v);
        add(l1,r1,x,l[v],tl,tm);add(l1,r1,x,r[v],tm+1,tr);
        pull(v);
    }
    int get(int l1,int r1,int v,int tl,int tr){
        if(v==-1) return 0;
        if(tl>=l1 && tr<=r1){
//            cerr<<"ALO "<<t[v]<<endl;
            return t[v];
        }
        if(tl>r1 || tr<l1) return 0;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return max(get(l1,r1,l[v],tl,tm),get(l1,r1,r[v],tm+1,tr));
    }
};
const int N=2e5+1;
vec<int> g[N];
segtree* seg[N];
set<int>* h[N];
int d;
//vec<pii> sons[N];

void dfs(int v,int gl){
//    sons[v].pb({0,v});
    int big=-1;
    for(auto &z : g[v]){
        dfs(z,gl+1);
        if(big==-1 || (int)(*h[z]).size() > (int)(*h[big]).size()) big=z;
    }
    if(big==-1){
        seg[v]=new segtree();
        h[v]=new set<int>();
    }
    else{
        seg[v]=seg[big];h[v]=h[big];
    }
    for(auto &z : g[v]){
        if(z==big) continue;
        vec<int>vc;
        for(auto &z : (*h[z])){
            (*h[v]).insert(z);vc.pb(z);
        }
        int lst=N;
        vec<pii>lel;
        vec<int>vls(sz(vc));
        for(int i=sz(vc)-1;i>=0;i--){
            int h=vc[i]-gl;
            int j=max(h,d-h);
            vls[i]=(*seg[z]).get(h+gl,N-1,0,0,N-1);
//            cerr<<"VL "<<vls[i]<<endl;
            lel.pb({vc[i],(*seg[v]).get(j+gl,N-1,0,0,N-1)+vls[i]});
//            cerr<<"VL "<<lel.back().s<<endl;
        }
        for(int i=0;i<sz(vc);i++){
            if(i){
//                cerr<<vls[i]<<' '<<vls[i-1]<<endl;
                assert(vls[i]<=vls[i-1]);
            }
            int h=vc[i]-gl;
            int j=d-h;
            if(j<h){
                int lft=j+gl,rgt=min(h+gl,lst-1);
                if(lft<=rgt) (*seg[v]).add(lft,rgt,vls[i],0,0,N-1);
                lst=lft;
            }
        }
        for(auto &z : lel) (*seg[v]).upd(z.f,z.s,0,0,N-1);
        (*seg[z]).clr();
        (*h[z]).clear();
    }
//    cerr<<"HEY "<<(*seg[v]).get(gl+d,N-1,0,0,N-1)<<endl;
    (*seg[v]).upd(gl,(*seg[v]).get(gl+d,N-1,0,0,N-1)+1,0,0,N-1);
    (*h[v]).insert(gl);
//    for(auto &z : (*h[v])){
//        cerr<<"DP "<<v<<' '<<z-gl<<' '<<(*seg[v]).get(z,z,0,0,N-1)<<endl;
//    }
}
//int dp[N][N];
//void dfs1(int v){
//    for(auto &z : g[v]){
//        dfs1(z);
//    }
//    int n=sz(g[v]);
//    vec<vec<int>>pref(n,vec<int>(d+1,0));
//    vec<vec<int>>suf(n,vec<int>(d+1,0));
//    for(int i=0;i<n;i++){
//        int u=g[v][i];
//        if(i+1<n){
//            for(int j=d;j>=0;j--){
//                pref[i+1][j]=pref[i][j]+dp[u][j];
//            }
//        }
//    }
//    for(int i=n-1;i>=0;i--){
//        int u=g[v][i];
//        if(i>0){
//            for(int j=d;j>=0;j--){
//                suf[i-1][j]=suf[i][j]+dp[u][j];
//            }
//        }
//    }
//    for(int m=0;m<=d;m++){
//        int mx=0;
//        int j=max(m,d-m-2);
//        for(int i=0;i<n;i++){
//            umax(mx,pref[i][j]+suf[i][j]+dp[g[v][i]][m]);
//        }
//        dp[v][m+1]=mx;
//    }
//    for(int i=N-2;i>=0;i--){
//        umax(dp[v][i],dp[v][i+1]);
//    }
//    umax(dp[v][0],dp[v][d]+1);
//}

signed main(){
    fast_ioi;
    int n=100;d=3;
    cin>>n>>d;
    bool dbg=0;
    for(int i=1;i<n;i++){
       int p;p=rng()%i;
        if(!dbg) cin>>p;
       g[p].pb(i);
       if(dbg)cout<<p<<endl;
    }
    auto solve=[&](){
        dfs(0,0);
        int ans=(*seg[0]).t[0];
        return ans;
    };
//    auto brute=[&](){
//        dfs1(0);
//        return dp[0][0];
//    };
    cout<<solve();
//    assert(solve()==brute());
    return 0;
}

/*
7 3
0
1
0
1
3
5
0

*/

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