QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#93596 | #4408. 燃烧的呐球 | chenshi# | 100 ✓ | 8926ms | 301936kb | C++ | 5.1kb | 2023-04-01 19:51:22 | 2023-04-01 19:51:23 |
Judging History
answer
#include<cstdio>
#include<utility>
#include<vector>
#include<iostream>
using namespace std;
const int o=1e6+10,O=4e6+10;
int n,m,p[o],X[o],Y[o],dfn[o],ed[o],tot,nfd[o*2],h[o],cnt,fa[o],s[o],tp,Tp[o],ptn[o],w[o],col[o];
int rt[o],ls[O],rs[O];long long ans;vector<int> vec[o];
int fr(int x){return fa[x]==x?x:fa[x]=fr(fa[x]);}
struct Edge{int v,p;}e[o];
inline void ad(int U,int V){e[++cnt].v=V;e[cnt].p=h[U];h[U]=cnt;}
struct info{
pair<int,int> fi,se;
info(int a=O,int b=0,int c=O,int d=0):fi(make_pair(a,b)),se(make_pair(c,d)){}
inline void upd(info b){
if(fi.first>b.fi.first) swap(fi,b.fi);
if(b.fi.first<=se.first&&col[b.fi.second]-col[fi.second]) se=b.fi;
if(b.se.first<=se.first&&col[b.se.second]-col[fi.second]) se=b.se;
}
}tmp,mn[O],Val[O],*st[O];
void dfs(int nw){
dfn[nw]=++tot;s[nfd[++cnt]=nw]=1;
for(int i=h[nw];i;i=e[i].p) dfs(e[i].v),s[nw]+=s[e[i].v];
ed[nw]=tot;nfd[++cnt]=-nw;
}
inline void upd(int x,const info&y,int d){
x=col[x];
if(y.fi.first+d<w[x]&&col[y.fi.second]-x) w[x]=y.fi.first+d,ptn[x]=y.fi.second;
if(y.se.first+d<w[x]&&col[y.se.second]-x) w[x]=y.se.first+d,ptn[x]=y.se.second;
}
void modify1(int&id,int pos,const info&val,int l=1,int r=n){
if(!id) mn[id=++cnt]=info(),ls[id]=rs[id]=0;
st[++tp]=mn+id;Val[tp]=*st[tp];mn[id].upd(val);
if(l==r) return;
int md=l+r>>1;
if(pos<=md) modify1(ls[id],pos,val,l,md);
else modify1(rs[id],pos,val,md+1,r);
}
void query1(int id,int ql,int qr,int l=1,int r=n){
if(!id) return;
if(ql<=l&&r<=qr){tmp.upd(mn[id]);return;}
int md=l+r>>1;
if(ql<=md) query1(ls[id],ql,qr,l,md);
if(md<qr) query1(rs[id],ql,qr,md+1,r);
}
void modify2(int&id,int ql,int qr,const info&val,int l=1,int r=n){
if(!id) mn[id=++cnt]=info(),ls[id]=rs[id]=0;
if(ql<=l&&r<=qr){st[++tp]=mn+id;Val[tp]=*st[tp];mn[id].upd(val);return;}
int md=l+r>>1;
if(ql<=md) modify2(ls[id],ql,qr,val,l,md);
if(md<qr) modify2(rs[id],ql,qr,val,md+1,r);
}
void query2(int id,int pos,int l=1,int r=n){
if(!id) return;
tmp.upd(mn[id]);
if(l==r) return;
int md=l+r>>1;
if(pos<=md) query2(ls[id],pos,l,md);
else query2(rs[id],pos,md+1,r);
}
int merge(int x,int y){
if(!x||!y) return x|y;
mn[x].upd(mn[y]);
ls[x]=merge(ls[x],ls[y]);rs[x]=merge(rs[x],rs[y]);
return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n;++i) scanf("%d",&p[i]),ad(p[i],i);
for(int i=1;i<=m;++i) scanf("%d%d",&X[i],&Y[i]),vec[X[i]].push_back(i),fa[i]=i;
cnt=0;dfs(1);
for(int num=m;num>1;){
for(int i=1;i<=m;++i) ptn[i]=0,w[i]=O,col[i]=fr(i);
//case1:sxi+syi+sxj+syj
tmp=info();
for(int i=1;i<=m;++i) tmp.upd(info(s[X[i]]+s[Y[i]],i));
for(int i=1;i<=m;++i) upd(i,tmp,s[X[i]]+s[Y[i]]);
//case2:sxi+syi+sxj-syj
rt[0]=cnt=tp=0;
for(int i=1;i<=m;++i) modify1(rt[0],dfn[Y[i]],info(s[X[i]]-s[Y[i]],i));
for(int i=1;i<=m;++i) tmp=info(),query1(rt[0],dfn[Y[i]],ed[Y[i]]),upd(i,tmp,s[X[i]]+s[Y[i]]);
//case3:sxi-syi+sxj+syj
rt[0]=cnt=tp=0;
for(int i=1;i<=m;++i) modify2(rt[0],dfn[Y[i]],ed[Y[i]],info(s[X[i]]+s[Y[i]],i));
for(int i=1;i<=m;++i) tmp=info(),query2(rt[0],dfn[Y[i]]),upd(i,tmp,s[X[i]]-s[Y[i]]);
//case4:sxi+syi-sxj+syj
for(int i=1;i<=n;++i) mn[i]=info();
for(int i=1;i<=m;++i) mn[X[i]].upd(info(-s[X[i]]+s[Y[i]],i));
for(int i=n;i>1;--i) mn[p[i]].upd(mn[i]);
for(int i=1;i<=m;++i) upd(i,mn[X[i]],s[X[i]]+s[Y[i]]);
//case5:-sxi+syi+sxj+syj
for(int i=1;i<=n;++i) mn[i]=info();
for(int i=1;i<=m;++i) mn[X[i]].upd(info(s[X[i]]+s[Y[i]],i));
for(int i=2;i<=n;++i) mn[i].upd(mn[p[i]]);
for(int i=1;i<=m;++i) upd(i,mn[X[i]],-s[X[i]]+s[Y[i]]);
//case6:sxi+syi-sxj-syj
cnt=tp=0;
for(int i=1;i<=n;++i) rt[i]=0;
for(int i=1;i<=m;++i) modify1(rt[X[i]],dfn[Y[i]],info(-s[X[i]]-s[Y[i]],i));
for(int i=n;i;--i){
for(int j=vec[i].size(),t;j--;)
t=vec[i][j],tmp=info(),query1(rt[i],dfn[Y[t]],ed[Y[t]]),upd(t,tmp,s[X[t]]+s[Y[t]]);
if(i>1) rt[p[i]]=merge(rt[p[i]],rt[i]);
}
//case7:sxi-syi-sxj+syj
cnt=tp=0;
for(int i=1;i<=n;++i) rt[i]=0;
for(int i=1;i<=m;++i) modify2(rt[X[i]],dfn[Y[i]],ed[Y[i]],info(-s[X[i]]+s[Y[i]],i));
for(int i=n;i;--i){
for(int j=vec[i].size(),t;j--;)
t=vec[i][j],tmp=info(),query2(rt[i],dfn[Y[t]]),upd(t,tmp,s[X[t]]-s[Y[t]]);
if(i>1) rt[p[i]]=merge(rt[p[i]],rt[i]);
}
//case8:-sxi+syi+sxj-syj
rt[0]=cnt=tp=0;
for(int i=1,u;i<=n*2;++i)
if(nfd[i]<0) for(;tp>Tp[-nfd[i]];--tp) *st[tp]=Val[tp];
else{
Tp[u=nfd[i]]=tp;
for(int j=vec[u].size(),t;j--;) t=vec[u][j],modify1(rt[0],dfn[Y[t]],info(s[X[t]]-s[Y[t]],t));
for(int j=vec[u].size(),t;j--;)
t=vec[u][j],tmp=info(),query1(rt[0],dfn[Y[t]],ed[Y[t]]),upd(t,tmp,-s[X[t]]+s[Y[t]]);
}
//case9:-sxi-syi+sxj+syj
rt[0]=cnt=tp=0;
for(int i=1,u;i<=n*2;++i)
if(nfd[i]<0) for(;tp>Tp[-nfd[i]];--tp) *st[tp]=Val[tp];
else{
Tp[u=nfd[i]]=tp;
for(int j=vec[u].size(),t;j--;) t=vec[u][j],modify2(rt[0],dfn[Y[t]],ed[Y[t]],info(s[X[t]]+s[Y[t]],t));
for(int j=vec[u].size(),t;j--;)
t=vec[u][j],tmp=info(),query2(rt[0],dfn[Y[t]]),upd(t,tmp,-s[X[t]]-s[Y[t]]);
}
//boruvka
for(int i=1;i<=m;++i) if(fa[i]==i&&i-fr(ptn[i])) ans+=w[i],fa[fr(i)]=fr(ptn[i]),--num;
}
printf("%lld",ans);
return 0;
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 39ms
memory: 154212kb
Test #2:
score: 0
Accepted
time: 27ms
memory: 153644kb
Test #3:
score: 0
Accepted
time: 20ms
memory: 154284kb
Test #4:
score: 0
Accepted
time: 26ms
memory: 152712kb
Test #5:
score: 0
Accepted
time: 49ms
memory: 153856kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 1304ms
memory: 205420kb
Test #7:
score: 0
Accepted
time: 900ms
memory: 202960kb
Test #8:
score: 0
Accepted
time: 688ms
memory: 202804kb
Test #9:
score: 0
Accepted
time: 670ms
memory: 203028kb
Test #10:
score: 0
Accepted
time: 899ms
memory: 202844kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 3009ms
memory: 215668kb
Test #12:
score: 0
Accepted
time: 2053ms
memory: 215036kb
Test #13:
score: 0
Accepted
time: 1673ms
memory: 214316kb
Test #14:
score: 0
Accepted
time: 1550ms
memory: 214520kb
Test #15:
score: 0
Accepted
time: 1937ms
memory: 214888kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 451ms
memory: 164956kb
Test #17:
score: 0
Accepted
time: 550ms
memory: 165516kb
Test #18:
score: 0
Accepted
time: 357ms
memory: 164400kb
Test #19:
score: 0
Accepted
time: 456ms
memory: 165680kb
Test #20:
score: 0
Accepted
time: 451ms
memory: 164276kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 8821ms
memory: 301780kb
Test #22:
score: 0
Accepted
time: 8882ms
memory: 301936kb
Test #23:
score: 0
Accepted
time: 8921ms
memory: 301932kb
Test #24:
score: 0
Accepted
time: 8926ms
memory: 301772kb
Test #25:
score: 0
Accepted
time: 8588ms
memory: 301728kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 2462ms
memory: 229140kb
Test #27:
score: 0
Accepted
time: 2529ms
memory: 229140kb
Test #28:
score: 0
Accepted
time: 2533ms
memory: 229068kb
Test #29:
score: 0
Accepted
time: 2504ms
memory: 229232kb
Test #30:
score: 0
Accepted
time: 2532ms
memory: 229136kb
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: 6036ms
memory: 236040kb
Test #32:
score: 0
Accepted
time: 3684ms
memory: 235032kb
Test #33:
score: 0
Accepted
time: 2983ms
memory: 233708kb
Test #34:
score: 0
Accepted
time: 3106ms
memory: 233908kb
Test #35:
score: 0
Accepted
time: 3774ms
memory: 234228kb
Test #36:
score: 0
Accepted
time: 6238ms
memory: 236144kb
Test #37:
score: 0
Accepted
time: 4152ms
memory: 234892kb
Test #38:
score: 0
Accepted
time: 3250ms
memory: 233680kb
Test #39:
score: 0
Accepted
time: 3129ms
memory: 233972kb
Test #40:
score: 0
Accepted
time: 3877ms
memory: 234288kb