QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882539#4408. 燃烧的呐球TulipeNoire100 ✓7281ms798320kbC++148.6kb2025-02-05 09:12:002025-02-05 09:12:01

Judging History

This is the latest submission verdict.

  • [2025-02-05 09:12:01]
  • Judged
  • Verdict: 100
  • Time: 7281ms
  • Memory: 798320kb
  • [2025-02-05 09:12:00]
  • Submitted

answer

#include<bits/stdc++.h>
#define lowbit(x) ((x)&-(x))
using namespace std;
using LL=long long;
using pii=pair<int,int>;
struct Info {
    int mn,mpos,se,spos;
    inline Info operator+(const int t) {
        return {mn+t,mpos,se+t,spos};
    }
}INF;
inline Info min(Info x,Info y) {
    if (x.mpos==y.mpos) {
        if (x.se<y.se) return {min(x.mn,y.mn),x.mpos,x.se,x.spos};
        return {min(x.mn,y.mn),x.mpos,y.se,y.spos};
    }
    if (x.mn<y.mn) {
        if (x.se<y.mn) return x;
        return {x.mn,x.mpos,y.mn,y.mpos};
    }
    if (y.se<x.mn) return y;
    return {y.mn,y.mpos,x.mn,x.mpos};
}
inline void chkmin(Info &x,Info y) {
    x=min(x,y);
}
inline int read() {
    int f=0;
    char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) f=f*10+(c-'0'),c=getchar();
    return f;
}
const int N=1000005,M=100005,inf=1e9;
int n,m,fa[N],qx[M],qy[M];
vector<int>G[N];
int siz[N],tot,dfn[N],efn[N];
struct DSU {
    int fa[M];
    inline void init(int n) {
        for (int i=1;i<=n;i++) fa[i]=i;
    }
    int Find(int x) {
        if (fa[x]==x) return x;
        return fa[x]=Find(fa[x]);
    }
    inline void Merge(int x,int y) {
        fa[Find(x)]=Find(y);
    }
}D;
void dfs0(int p) {
    siz[p]=1,dfn[p]=++tot;
    for (auto x:G[p]) dfs0(x),siz[p]+=siz[x];
    efn[p]=tot;
}
int dcnt,col[M];
Info ans[M];
inline void solve1() {
    Info res=INF;
    for (int i=1;i<=m;i++) chkmin(res,{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
    for (int i=1;i<=m;i++) ans[i]=res+(siz[qx[i]]+siz[qy[i]]);
}
int nowid;
struct Ops {
    int id,pos;
    Info origin;
};
struct SGT1 {
    Info dat[N<<2];
    stack<Ops>stk;
    void build(int p,int l,int r) {
        dat[p]=INF;
        if (l==r) return;
        int mid=(l+r)>>1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    void update(int p,int l,int r,int x,Info d) {
        if (nowid) stk.push({nowid,p,dat[p]});
        chkmin(dat[p],d);
        if (l==r) return;
        int mid=(l+r)>>1;
        if (x<=mid) update(p<<1,l,mid,x,d);
        else update(p<<1|1,mid+1,r,x,d);
    }
    Info qmin(int p,int l,int r,int L,int R) {
        if (L<=l&&r<=R) return dat[p];
        int mid=(l+r)>>1;
        Info res={inf,0};
        if (L<=mid) chkmin(res,qmin(p<<1,l,mid,L,R));
        if (R>mid) chkmin(res,qmin(p<<1|1,mid+1,r,L,R));
        return res;
    }
    inline void rollback(int t) {
        while (!stk.empty()&&stk.top().id==t) dat[stk.top().pos]=stk.top().origin,stk.pop();
    }
}T1x,T1y,T1;
struct SGT2 {
    Info tag[N<<2];
    stack<Ops>stk;
    void build(int p,int l,int r) {
        tag[p]={inf,0};
        if (l==r) return;
        int mid=(l+r)>>1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    }
    void update(int p,int l,int r,int L,int R,Info d) {
        if (L<=l&&r<=R) {
            if (nowid) stk.push({nowid,p,tag[p]});
            chkmin(tag[p],d);
            return;
        }
        int mid=(l+r)>>1;
        if (L<=mid) update(p<<1,l,mid,L,R,d);
        if (R>mid) update(p<<1|1,mid+1,r,L,R,d);
    }
    Info qmin(int p,int l,int r,int x) {
        if (l==r) return tag[p];
        int mid=(l+r)>>1;
        if (x<=mid) return min(tag[p],qmin(p<<1,l,mid,x));
        return min(tag[p],qmin(p<<1|1,mid+1,r,x));
    }
    inline void rollback(int t) {
        while (!stk.empty()&&stk.top().id==t) tag[stk.top().pos]=stk.top().origin,stk.pop();
    }
}T2x,T2y,T2;
inline void solve2() {
    nowid=0,T1x.build(1,1,n),T1y.build(1,1,n),T2x.build(1,1,n),T2y.build(1,1,n);
    for (int i=1;i<=m;i++) {
        T1x.update(1,1,n,dfn[qx[i]],{-siz[qx[i]]+siz[qy[i]],col[i],inf,0});
        T1y.update(1,1,n,dfn[qy[i]],{-siz[qy[i]]+siz[qx[i]],col[i],inf,0});
        T2x.update(1,1,n,dfn[qx[i]],efn[qx[i]],{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
        T2y.update(1,1,n,dfn[qy[i]],efn[qy[i]],{siz[qx[i]]+siz[qy[i]],col[i],inf,0});
    }
    for (int i=1;i<=m;i++) {
        chkmin(ans[i],T1x.qmin(1,1,n,dfn[qx[i]],efn[qx[i]])+(siz[qx[i]]+siz[qy[i]]));
        chkmin(ans[i],T1y.qmin(1,1,n,dfn[qy[i]],efn[qy[i]])+(siz[qx[i]]+siz[qy[i]]));
        chkmin(ans[i],T2x.qmin(1,1,n,dfn[qx[i]])+(-siz[qx[i]]+siz[qy[i]]));
        chkmin(ans[i],T2y.qmin(1,1,n,dfn[qy[i]])+(-siz[qy[i]]+siz[qx[i]]));
    }
}
vector<int>vec[N];
inline void rollback(int p) {
    T1.rollback(p),T2.rollback(p);
}
int cnt1,cnt2,rt1[N],rt2[N];
struct Node {
    int lc,rc;
    Info dat;
}tr1[M<<6],tr2[M<<6];
void update1(int &p,int l,int r,int x,Info d) {
    if (!p) p=++cnt1,tr1[p].dat=d;
    else chkmin(tr1[p].dat,d);
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) update1(tr1[p].lc,l,mid,x,d);
    else update1(tr1[p].rc,mid+1,r,x,d);
}
void update2(int &p,int l,int r,int L,int R,Info d) {
    if (!p) p=++cnt2,tr2[p].dat=INF;
    if (L<=l&&r<=R) {
        chkmin(tr2[p].dat,d);
        return;
    }
    int mid=(l+r)>>1;
    if (L<=mid) update2(tr2[p].lc,l,mid,L,R,d);
    if (R>mid) update2(tr2[p].rc,mid+1,r,L,R,d);
}
int Merge1(int p,int q,int l,int r) {
    if (!p||!q) return p+q;
    chkmin(tr1[p].dat,tr1[q].dat);
    int mid=(l+r)>>1;
    tr1[p].lc=Merge1(tr1[p].lc,tr1[q].lc,l,mid);
    tr1[p].rc=Merge1(tr1[p].rc,tr1[q].rc,mid+1,r);
    return p;
}
int Merge2(int p,int q,int l,int r) {
    if (!p||!q) return p+q;
    chkmin(tr2[p].dat,tr2[q].dat);
    int mid=(l+r)>>1;
    tr2[p].lc=Merge2(tr2[p].lc,tr2[q].lc,l,mid);
    tr2[p].rc=Merge2(tr2[p].rc,tr2[q].rc,mid+1,r);
    return p;
}
Info qmin1(int p,int l,int r,int L,int R) {
    if (!p) return INF;
    if (L<=l&&r<=R) return tr1[p].dat;
    int mid=(l+r)>>1;
    Info res=INF;
    if (L<=mid) chkmin(res,qmin1(tr1[p].lc,l,mid,L,R));
    if (R>mid) chkmin(res,qmin1(tr1[p].rc,mid+1,r,L,R));
    return res;
}
Info qmin2(int p,int l,int r,int x) {
    if (!p) return INF;
    if (l==r) return tr2[p].dat;
    int mid=(l+r)>>1;
    if (x<=mid) return min(tr2[p].dat,qmin2(tr2[p].lc,l,mid,x));
    return min(tr2[p].dat,qmin2(tr2[p].rc,mid+1,r,x));
}
void dfs1(int p) {
    nowid=p;
    for (auto x:vec[p]) {
        T1.update(1,1,n,dfn[qy[x]],{siz[p]-siz[qy[x]],col[x],inf,0});
        T2.update(1,1,n,dfn[qy[x]],efn[qy[x]],{siz[p]+siz[qy[x]],col[x],inf,0});
        update1(rt1[p],1,n,dfn[qy[x]],{-siz[p]-siz[qy[x]],col[x],inf,0});
        update2(rt2[p],1,n,dfn[qy[x]],efn[qy[x]],{-siz[p]+siz[qy[x]],col[x],inf,0});
    }
    for (auto x:vec[p]) {
        chkmin(ans[x],T1.qmin(1,1,n,dfn[qy[x]],efn[qy[x]])+(-siz[p]+siz[qy[x]]));
        chkmin(ans[x],T2.qmin(1,1,n,dfn[qy[x]])+(-siz[p]-siz[qy[x]]));
    }
    for (auto x:G[p]) dfs1(x),rt1[p]=Merge1(rt1[p],rt1[x],1,n),rt2[p]=Merge2(rt2[p],rt2[x],1,n);
    rollback(p);
    for (auto x:vec[p]) {
        chkmin(ans[x],qmin1(rt1[p],1,n,dfn[qy[x]],efn[qy[x]])+(siz[p]+siz[qy[x]]));
        chkmin(ans[x],qmin2(rt2[p],1,n,dfn[qy[x]])+(siz[p]-siz[qy[x]]));
    }
}
inline void Clear() {
    for (int i=1;i<=cnt1;i++) tr1[i]={};
    for (int i=1;i<=cnt2;i++) tr2[i]={};
    cnt1=cnt2=0;
    for (int i=1;i<=n;i++) rt1[i]=rt2[i]=0;
}
inline void solve3() {
    Clear(),dfs1(1);
}
inline LL solve() {
    for (int i=1;i<=m;i++) col[i]=D.Find(i);
    solve1(),solve2(),solve3();
    // for (int i=1;i<=m;i++) {
    //     ans[i]=INF;
    //     for (int j=1;j<=m;j++) {
    //         int sum=0;
    //         if (dfn[qx[i]]<=dfn[qx[j]]&&dfn[qx[j]]<=efn[qx[i]]||dfn[qx[j]]<=dfn[qx[i]]&&dfn[qx[i]]<=efn[qx[j]]) sum+=abs(siz[qx[i]]-siz[qx[j]]);
    //         else sum+=siz[qx[i]]+siz[qx[j]];
    //         if (dfn[qy[i]]<=dfn[qy[j]]&&dfn[qy[j]]<=efn[qy[i]]||dfn[qy[j]]<=dfn[qy[i]]&&dfn[qy[i]]<=efn[qy[j]]) sum+=abs(siz[qy[i]]-siz[qy[j]]);
    //         else sum+=siz[qy[i]]+siz[qy[j]];
    //         chkmin(ans[i],{sum,col[j],inf,0});
    //     }
    // }
    LL sum=0;
    // for (int i=1;i<=m;i++) cout<<i<<' '<<col[i]<<' '<<ans[i].se<<' '<<ans[i].spos<<"\n";
    for (int i=1;i<=m;i++) if (i!=col[i]) chkmin(ans[col[i]],ans[i]);
    for (int i=1;i<=m;i++) {
        if (i!=col[i]) continue;
        if (ans[i].spos==i) swap(ans[i].mn,ans[i].se),swap(ans[i].mpos,ans[i].spos);
        int t=ans[i].spos;
        if (D.Find(i)!=D.Find(t)) D.Merge(i,t),sum+=ans[i].se,dcnt--;
    }
    return sum;
}
inline LL Boruvka() {
    LL sum=0;
    while (dcnt>1) sum+=solve();
    return sum;
}
int main() {
    INF={inf,0,inf,-1};
    n=read(),dcnt=m=read(),D.init(m),T1.build(1,1,n),T2.build(1,1,n);
    for (int i=2;i<=n;i++) G[fa[i]=read()].push_back(i);
    dfs0(1);
    for (int i=1;i<=m;i++) qx[i]=read(),qy[i]=read(),vec[qx[i]].push_back(i);
    printf("%d",Boruvka());
    return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 15ms
memory: 77952kb

Test #2:

score: 10
Accepted
time: 16ms
memory: 83944kb

Test #3:

score: 10
Accepted
time: 14ms
memory: 80000kb

Test #4:

score: 10
Accepted
time: 17ms
memory: 80000kb

Test #5:

score: 10
Accepted
time: 14ms
memory: 77956kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1355ms
memory: 333684kb

Test #7:

score: 10
Accepted
time: 740ms
memory: 328860kb

Test #8:

score: 10
Accepted
time: 517ms
memory: 320732kb

Test #9:

score: 10
Accepted
time: 531ms
memory: 329980kb

Test #10:

score: 10
Accepted
time: 683ms
memory: 326476kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 2637ms
memory: 365252kb

Test #12:

score: 10
Accepted
time: 1542ms
memory: 360616kb

Test #13:

score: 10
Accepted
time: 1192ms
memory: 354404kb

Test #14:

score: 10
Accepted
time: 1212ms
memory: 359412kb

Test #15:

score: 10
Accepted
time: 1450ms
memory: 358412kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 520ms
memory: 91972kb

Test #17:

score: 20
Accepted
time: 638ms
memory: 87556kb

Test #18:

score: 20
Accepted
time: 467ms
memory: 89236kb

Test #19:

score: 20
Accepted
time: 485ms
memory: 88812kb

Test #20:

score: 20
Accepted
time: 623ms
memory: 89508kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 7281ms
memory: 796352kb

Test #22:

score: 10
Accepted
time: 7159ms
memory: 796284kb

Test #23:

score: 10
Accepted
time: 7180ms
memory: 796232kb

Test #24:

score: 10
Accepted
time: 7133ms
memory: 798320kb

Test #25:

score: 10
Accepted
time: 7119ms
memory: 796252kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1567ms
memory: 392340kb

Test #27:

score: 10
Accepted
time: 1583ms
memory: 394392kb

Test #28:

score: 10
Accepted
time: 1602ms
memory: 392468kb

Test #29:

score: 10
Accepted
time: 1581ms
memory: 396560kb

Test #30:

score: 10
Accepted
time: 1582ms
memory: 392340kb

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: 4496ms
memory: 422080kb

Test #32:

score: 30
Accepted
time: 2411ms
memory: 415188kb

Test #33:

score: 30
Accepted
time: 1951ms
memory: 404996kb

Test #34:

score: 30
Accepted
time: 1995ms
memory: 412244kb

Test #35:

score: 30
Accepted
time: 2304ms
memory: 413132kb

Test #36:

score: 30
Accepted
time: 4495ms
memory: 422228kb

Test #37:

score: 30
Accepted
time: 2401ms
memory: 415316kb

Test #38:

score: 30
Accepted
time: 2011ms
memory: 404864kb

Test #39:

score: 30
Accepted
time: 2046ms
memory: 412244kb

Test #40:

score: 30
Accepted
time: 2273ms
memory: 411088kb