Submission #1256504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256504		cattuong	Magic Tree (CEOI19_magictree)	C++20	42 / 100	62 ms	23364 KiB

magictree

/*❤️ I LOVE CATTUONG ❤️*/
//
#include <bits/stdc++.h>
#define CatTuong ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,K;
int hed[N],nxt[N*2],fr[N*2],cnt1,dist[N],weight[N],par[N],add[4*N],mini[4*N],maxi[4*N];
int lef[4*N],rig[4*N],cnt,stk[4*N],tp;
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
int NODE(){
    int id=(tp?stk[--tp]:++cnt);
    lef[id]=rig[id]=mini[id]=maxi[id]=add[id]=0;
    return id;
}
void rec(int u){
    if(!u)
        return;
    stk[tp++]=u;
    rec(lef[u]);
    rec(rig[u]);
}
void push(int u){
    mini[u]=Min(mini[lef[u]]+add[lef[u]],mini[rig[u]]+add[rig[u]]);
    maxi[u]=Max(maxi[lef[u]]+add[lef[u]],maxi[rig[u]]+add[rig[u]]);
    if(mini[u]==maxi[u]){
        rec(lef[u]);
        rec(rig[u]);
        lef[u]=rig[u]=0;
    }
}
inline bool uniform(int u){return mini[u]==maxi[u];}
int join(int a,int b){
    if(!a||!b) return a^b;
    if(uniform(a)){
        add[b]+=mini[a]+add[a];
        return b;
    }
    if(uniform(b)){
        add[a]+=mini[b]+add[b];
        return a;
    }
    lef[a]=join(lef[a],lef[b]);
    rig[a]=join(rig[a],rig[b]);
    push(a);
    add[a]+=add[b];
    return a;
}
int calc(int u,int l,int r,int pos){
    if(uniform(u))
        return add[u]+mini[u];
    int mid=(l+r)>>1;
    if(pos<=mid)
        return add[u]+calc(lef[u],l,mid,pos);
    return add[u]+calc(rig[u],mid+1,r,pos);
}
void update(int u,int l,int r,int ql,int qr,int val){
    val-=add[u];
    if(mini[u]>=val)
        return;
    if(ql<=l && r<=qr && maxi[u]<=val){
        mini[u]=maxi[u]=val;
        rec(lef[u]);
        rec(rig[u]);
        lef[u]=rig[u]=0;
        return;
    }
    if(uniform(u)){
        lef[u]=NODE();
        rig[u]=NODE();
        mini[lef[u]]=mini[rig[u]]=maxi[lef[u]]=maxi[rig[u]]=maxi[u];
    }
    int mid=(l+r)>>1;
    if(ql<=mid) update(lef[u],l,mid,ql,qr,val);
    if(qr>mid) update(rig[u],mid+1,r,ql,qr,val);
    push(u);
}
void add_edge(int u,int v){
    fr[cnt1]=v;
    nxt[cnt1]=hed[u];
    hed[u]=cnt1++;
}
void dfs(int u,int p){
    par[u]=NODE();
    for(int i=hed[u];~i;i=nxt[i]){
        int v=fr[i];
        if(v==p)
            continue;
        dfs(v,u);
        par[u]=join(par[u],par[v]);
    }
    if(dist[u]!=-1){
        int cur=calc(par[u],1,K,dist[u]);
        update(par[u],1,K,dist[u],K,(int)weight[u]+cur);
    }
}
signed main(){
    #define Tuong "cattuong"
//    freopen(Tuong".inp","r",stdin);
//    freopen(Tuong".out","w",stdout);
    CatTuong
    cin>>n>>m>>K;
    for(int i=1;i<=n;i++)
        hed[i]=-1;
    cnt1=0;
    for(int i=2;i<=n;i++){
        int p;cin>>p;
        add_edge(p,i);
        add_edge(i,p);
    }
    for(int i=1;i<=n;i++)
        dist[i]=-1;
    for(int i=1;i<=m;i++){
        int v,d,w;cin>>v>>d>>w;
        dist[v]=d;
        weight[v]=w;
    }
    cnt=0;tp=0;
    dfs(1,0);
    int ans=0;
    if(par[1])
        ans=add[par[1]]+maxi[par[1]];
    cout<<ans<<'\n';
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 16
• Subtask 6: 13 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17