QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#884886#4408. 燃烧的呐球binbin100 ✓8735ms1404148kbC++1410.8kb2025-02-06 11:32:502025-02-06 11:32:57

Judging History

This is the latest submission verdict.

  • [2025-02-06 11:32:57]
  • Judged
  • Verdict: 100
  • Time: 8735ms
  • Memory: 1404148kb
  • [2025-02-06 11:32:50]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define inf 1e9
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

const int maxn=1e6+5;

int n,m,cok;
int fa[maxn],dfn[maxn],siz[maxn],hso[maxn];

ll ans;

pii p[maxn],cho[maxn];

vector<int>E[maxn],Y[maxn],X[maxn];

struct DSU
{
    int f[maxn];
    inline void init(int n){for(int i=1;i<=n;i++) f[i]=i;}
    inline int fr(int u){return u==f[u]?u:f[u]=fr(f[u]);}
    inline bool merge(int u,int v){u=fr(u),v=fr(v);if(u==v) return 0;f[u]=v;return 1;}
}F;
struct nodeval
{
    pii p[2];
    inline void init(){p[0]=p[1]={inf,0};}
}val[maxn];

inline void dfs(int u)
{
    dfn[u]=++cok;siz[u]=1;
    for(int v:E[u])
    {
        dfs(v),siz[u]+=siz[v];
        if(siz[hso[u]]<siz[v]) hso[u]=v;
    }
}
inline void work(nodeval &tmp,pii i)
{
    if(tmp.p[0].se==i.se) tmp.p[0]=min(tmp.p[0],i);
    else
    {
        if(tmp.p[0].fi>i.fi) tmp.p[1]=tmp.p[0],tmp.p[0]=i;
        else tmp.p[1]=min(tmp.p[1],i);
    }
}
inline void Work(nodeval &tmp1,nodeval tmp2){work(tmp1,tmp2.p[0]),work(tmp1,tmp2.p[1]);}

namespace Case1//not not
{
    nodeval res;
    inline void solve()
    {
        res.init();
        for(int i=1;i<=m;i++) work(res,{siz[p[i].fi]+siz[p[i].se],F.fr(i)});
        for(int i=1;i<=m;i++)
        {
            work(val[i],{res.p[0].fi+siz[p[i].fi]+siz[p[i].se],res.p[0].se});
            work(val[i],{res.p[1].fi+siz[p[i].fi]+siz[p[i].se],res.p[1].se});
        }
    }
}
namespace Case2//fa not
{
    nodeval res[maxn];
    inline void dfs(int u)
    {
        for(int v:E[u])
        {
            dfs(v);
            Work(res[u],res[v]);
        }
        for(int v:X[u]) work(res[u],{-siz[p[v].fi]+siz[p[v].se],F.fr(v)});
        for(int v:X[u])
        {
            int tmp=siz[p[v].fi]+siz[p[v].se];
            work(val[v],{res[u].p[0].fi+tmp,res[u].p[0].se});
            work(val[v],{res[u].p[1].fi+tmp,res[u].p[1].se});
        }
    }
    inline void solve()
    {
        for(int i=1;i<=n;i++) res[i].init();
        dfs(1);
    }
}
namespace Case3//son not
{
    nodeval res[maxn];
    inline void dfs(int u)
    {
        for(int v:X[u]) work(res[u],{siz[p[v].fi]+siz[p[v].se],F.fr(v)});
        for(int v:X[u])
        {
            int tmp=-siz[p[v].fi]+siz[p[v].se];
            work(val[v],{res[u].p[0].fi+tmp,res[u].p[0].se});
            work(val[v],{res[u].p[1].fi+tmp,res[u].p[1].se});
        }
        for(int v:E[u])
        {
            Work(res[v],res[u]);
            dfs(v);
        }
    }
    inline void solve()
    {
        for(int i=1;i<=n;i++) res[i].init();
        dfs(1);
    }
}
namespace Case4//fa fa
{
    int rt[maxn];
    namespace linetree
    {
        #define lch(p) tr[p].lch
        #define rch(p) tr[p].rch
        int tot=0;
        struct{nodeval val;int lch,rch;}tr[maxn*20];
        inline int newnode(){tot++;lch(tot)=rch(tot)=0;tr[tot].val.init();return tot;}
        inline void pushup(int p)
        {
            Work(tr[p].val,tr[lch(p)].val);
            Work(tr[p].val,tr[rch(p)].val);
        }
        inline void insert(int &p1,int l,int r,int pos,int id)
        {
            if(!p1) p1=newnode();
            if(l==r)
            {
                work(tr[p1].val,{-siz[p[id].fi]-siz[p[id].se],F.fr(id)});
                return ;
            }
            int mid=(l+r)>>1;
            if(pos<=mid) insert(lch(p1),l,mid,pos,id);
            else insert(rch(p1),mid+1,r,pos,id);
            pushup(p1);
        }
        inline nodeval qry(int p,int l,int r,int lx,int rx)
        {
            nodeval res;res.init();
            if(r<lx||l>rx||!p) return res;
            if(lx<=l&&r<=rx) return tr[p].val;
            int mid=(l+r)>>1;
            Work(res,qry(lch(p),l,mid,lx,rx));
            Work(res,qry(rch(p),mid+1,r,lx,rx));
            return res;
        }
        inline void merge(int &p,int lp,int rp,int l,int r)
        {
            if(!lp||!rp) {p=lp+rp;return ;}
            p=lp;
            if(l==r)
            {
                Work(tr[p].val,tr[rp].val);
                return ;
            }
            int mid=(l+r)>>1;
            merge(lch(p),lch(lp),lch(rp),l,mid);
            merge(rch(p),rch(lp),rch(rp),mid+1,r);
        }
        #undef lch
        #undef rch
    }
    inline void dfs(int u)
    {
        for(int v:E[u])
        {
            dfs(v);
            linetree::merge(rt[u],rt[u],rt[v],1,n);
        }
        for(int v:X[u]) linetree::insert(rt[u],1,n,dfn[p[v].se],v);
        for(int v:X[u])
        {
            int tmp=siz[p[v].fi]+siz[p[v].se];
            nodeval res=linetree::qry(rt[u],1,n,dfn[p[v].se],dfn[p[v].se]+siz[p[v].se]-1);
            work(val[v],{res.p[0].fi+tmp,res.p[0].se});
            work(val[v],{res.p[1].fi+tmp,res.p[1].se});
        }
    }
    inline void solve()
    {
        linetree::tot=0;linetree::tr[0].val.init();
        for(int i=1;i<=n;i++) rt[i]=0;
        dfs(1);
    }
}
namespace Case5//son fa
{
    int rt[maxn];
    namespace wzytree
    {
        #define lch(p) tr[p].lch
        #define rch(p) tr[p].rch
        int tot=0;
        struct treenode{int lch,rch;nodeval val;}tr[maxn*20];
        inline int newnode(){tot++;lch(tot)=rch(tot)=0;tr[tot].val.init();return tot;}
        inline void pushup(int p)
        {
            Work(tr[p].val,tr[lch(p)].val);
            Work(tr[p].val,tr[rch(p)].val);
        }
        inline void insert(int &p1,int p2,int l,int r,int pos,int id)
        {
            p1=newnode();
            tr[p1]=tr[p2];
            if(l==r)
            {
                work(tr[p1].val,{siz[p[id].fi]-siz[p[id].se],F.fr(id)});
                return ;
            }
            int mid=(l+r)>>1;
            if(pos<=mid) insert(lch(p1),lch(p2),l,mid,pos,id);
            else insert(rch(p1),rch(p2),mid+1,r,pos,id);
            pushup(p1);
        }
        inline nodeval qry(int p,int l,int r,int lx,int rx)
        {
            nodeval res;res.init();
            if(r<lx||l>rx||!p) return res;
            if(lx<=l&&r<=rx) return tr[p].val;
            int mid=(l+r)>>1;
            Work(res,qry(lch(p),l,mid,lx,rx));
            Work(res,qry(rch(p),mid+1,r,lx,rx));
            return res;
        }
    }
    inline void dfs(int u)
    {
        for(int v:X[u]) wzytree::insert(rt[u],rt[u],1,n,dfn[p[v].se],v);
        for(int v:X[u])
        {
            int tmp=-siz[p[v].fi]+siz[p[v].se];
            nodeval res=wzytree::qry(rt[u],1,n,dfn[p[v].se],dfn[p[v].se]+siz[p[v].se]-1);
            work(val[v],{res.p[0].fi+tmp,res.p[0].se});
            work(val[v],{res.p[1].fi+tmp,res.p[1].se});
        }
        for(int v:E[u])
        {
            rt[v]=rt[u];
            dfs(v);
        }
        #undef lch
        #undef rch
    }
    inline void solve()
    {
        wzytree::tot=0;wzytree::tr[0].val.init();
        for(int i=1;i<=n;i++) rt[i]=0;
        dfs(1);
    }
}
namespace Case6//son son
{
    struct node{int id;nodeval tmp;};
    stack<node>stkval,stksum;
    namespace g_bst
    {
        #define lch(p) tr[p].lch
        #define rch(p) tr[p].rch
        int cnt;
        struct treenode{int lch,rch,fa;nodeval sum,val;}tr[maxn];
        int id[maxn],sum[maxn];
        inline int cbuild(int lx,int rx)
        {
            int l=lx,r=rx,tmp=lx;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if((sum[mid]-sum[lx-1])*2<=(sum[rx]-sum[lx-1])) tmp=mid,l=mid+1;
                else r=mid-1;
            }
            int u=id[tmp];tr[u].sum.init(),tr[u].val.init();
            if(tmp+1<=rx) tr[rch(u)=cbuild(tmp+1,rx)].fa=u;
            if(tmp-1>=lx) tr[lch(u)=cbuild(lx,tmp-1)].fa=u;
            return u;
        }
        inline int build(int u)
        {
            int x=u;
            do for(int v:E[x])
                if(v!=hso[x]) tr[build(v)].fa=x;
            while(x=hso[x]);
            cnt=0;x=u;
            do
            {
                id[++cnt]=x;
                sum[cnt]=sum[cnt-1]+siz[x]-siz[hso[x]];
            }while(x=hso[x]);
            return cbuild(1,cnt);
        }
        inline void insert(int u,int id)
        {
            pii res={siz[p[id].fi]+siz[p[id].se],F.fr(id)};
            stkval.push({u,tr[u].val});work(tr[u].val,res);
            for(;u;u=tr[u].fa)
            {
                stksum.push({u,tr[u].sum});work(tr[u].sum,res);
                if(u!=lch(tr[u].fa)&&u!=rch(tr[u].fa)) break;
            }
        }
        inline nodeval qry(int u)
        {
            nodeval res;res=tr[u].val;
            Work(res,tr[lch(u)].sum);
            for(;tr[u].fa;u=tr[u].fa) if(u!=lch(tr[u].fa))
                Work(res,tr[lch(tr[u].fa)].sum),Work(res,tr[tr[u].fa].val);
            return res;
        }
        #undef lch
        #undef rch
    }
    inline void dfs(int u)
    {
        int lstval=stkval.size(),lstsum=stksum.size();
        for(int v:X[u])
            g_bst::insert(p[v].se,v);
        for(int v:X[u])
        {
            int tmp=-siz[p[v].fi]-siz[p[v].se];
            nodeval res=g_bst::qry(p[v].se);
            work(val[v],{res.p[0].fi+tmp,res.p[0].se});
            work(val[v],{res.p[1].fi+tmp,res.p[1].se});
        }
        for(int v:E[u]) dfs(v);
        while(lstval<stkval.size()) g_bst::tr[stkval.top().id].val=stkval.top().tmp,stkval.pop();
        while(lstsum<stksum.size()) g_bst::tr[stksum.top().id].sum=stksum.top().tmp,stksum.pop();
    }
    inline void init(){g_bst::build(1);g_bst::tr[0].sum.init();g_bst::tr[0].val.init();}
    inline void solve(){dfs(1);}
}

inline bool check()
{
    for(int i=2;i<=m;i++) if(F.fr(i)!=F.fr(i-1)) return 1;
    return 0;
}
inline void boruvka()
{
    for(int i=1;i<=m;i++) val[i].init();
    Case1::solve();Case2::solve();Case3::solve();
    Case4::solve();
    Case5::solve();
    Case6::solve();
    for(int i=1;i<=n;i++) swap(X[i],Y[i]);
    for(int i=1;i<=m;i++) swap(p[i].fi,p[i].se);
    Case2::solve();Case3::solve();
    Case5::solve();
    for(int i=1;i<=n;i++) swap(X[i],Y[i]);
    for(int i=1;i<=m;i++) swap(p[i].fi,p[i].se);
    for(int i=1;i<=m;i++) cho[i].fi=1e9,cho[i].se=0;
    for(int i=1;i<=m;i++)
        if(val[i].p[0].se!=F.fr(i)) cho[F.fr(i)]=min(val[i].p[0],cho[F.fr(i)]);
        else cho[F.fr(i)]=min(val[i].p[1],cho[F.fr(i)]);
    for(int i=1;i<=m;i++) if(F.fr(i)==i&&F.merge(i,cho[i].se)) ans+=cho[i].fi;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
    {
        scanf("%d",&fa[i]);
        E[fa[i]].emplace_back(i);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&p[i].fi,&p[i].se);
        X[p[i].fi].emplace_back(i);Y[p[i].se].emplace_back(i);
    }
    F.init(m);dfs(1);Case6::init();
    while(check()) boruvka();
    printf("%lld",ans);
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 52ms
memory: 1059248kb

Test #2:

score: 10
Accepted
time: 56ms
memory: 1057780kb

Test #3:

score: 10
Accepted
time: 61ms
memory: 1059180kb

Test #4:

score: 10
Accepted
time: 69ms
memory: 1056748kb

Test #5:

score: 10
Accepted
time: 63ms
memory: 1056416kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 4378ms
memory: 1137112kb

Test #7:

score: 10
Accepted
time: 2248ms
memory: 1130904kb

Test #8:

score: 10
Accepted
time: 1154ms
memory: 1126660kb

Test #9:

score: 10
Accepted
time: 1269ms
memory: 1131052kb

Test #10:

score: 10
Accepted
time: 1822ms
memory: 1128612kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 6271ms
memory: 1136212kb

Test #12:

score: 10
Accepted
time: 3782ms
memory: 1133900kb

Test #13:

score: 10
Accepted
time: 2054ms
memory: 1127212kb

Test #14:

score: 10
Accepted
time: 2259ms
memory: 1131868kb

Test #15:

score: 10
Accepted
time: 3092ms
memory: 1131200kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 634ms
memory: 1062988kb

Test #17:

score: 20
Accepted
time: 669ms
memory: 1063008kb

Test #18:

score: 20
Accepted
time: 410ms
memory: 1061436kb

Test #19:

score: 20
Accepted
time: 524ms
memory: 1063552kb

Test #20:

score: 20
Accepted
time: 633ms
memory: 1062328kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 8672ms
memory: 1402092kb

Test #22:

score: 10
Accepted
time: 8735ms
memory: 1404136kb

Test #23:

score: 10
Accepted
time: 8698ms
memory: 1402096kb

Test #24:

score: 10
Accepted
time: 8721ms
memory: 1404148kb

Test #25:

score: 10
Accepted
time: 8684ms
memory: 1403968kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1528ms
memory: 1119600kb

Test #27:

score: 10
Accepted
time: 1503ms
memory: 1119124kb

Test #28:

score: 10
Accepted
time: 1527ms
memory: 1121116kb

Test #29:

score: 10
Accepted
time: 1527ms
memory: 1119076kb

Test #30:

score: 10
Accepted
time: 1518ms
memory: 1120988kb

Subtask #7:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #31:

score: 30
Accepted
time: 7855ms
memory: 1140732kb

Test #32:

score: 30
Accepted
time: 4567ms
memory: 1141988kb

Test #33:

score: 30
Accepted
time: 2706ms
memory: 1143312kb

Test #34:

score: 30
Accepted
time: 2878ms
memory: 1146464kb

Test #35:

score: 30
Accepted
time: 3814ms
memory: 1145300kb

Test #36:

score: 30
Accepted
time: 7660ms
memory: 1149812kb

Test #37:

score: 30
Accepted
time: 4538ms
memory: 1147484kb

Test #38:

score: 30
Accepted
time: 2671ms
memory: 1141264kb

Test #39:

score: 30
Accepted
time: 2887ms
memory: 1150552kb

Test #40:

score: 30
Accepted
time: 3816ms
memory: 1145176kb