QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#884886 | #4408. 燃烧的呐球 | binbin | 100 ✓ | 8735ms | 1404148kb | C++14 | 10.8kb | 2025-02-06 11:32:50 | 2025-02-06 11:32:57 |
Judging History
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);
}
Details
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