QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#885609 | #4408. 燃烧的呐球 | cqbzxzj | 100 ✓ | 7213ms | 587000kb | C++14 | 7.2kb | 2025-02-06 16:34:29 | 2025-02-06 16:34:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int SZ=1<<20;
char buf[SZ],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++)
ll read(){
ll n=0; bool m=0;
char c=gc();
while(c<'0'||c>'9')m=c=='-',c=gc();
while(c>='0'&&c<='9')n=(n<<3)+(n<<1)+(c^'0'),c=gc();
return m?-n:n;
}
const int N=1e6+5,M=1e5+5,K=M<<5,inf=0x3f3f3f3f;
int n,m;
namespace dsu{
int fa[M],sz[M];
void init(){
for(int i=1;i<=m;i++)fa[i]=i,sz[i]=1;
}
int find(int u){
return fa[u]==u?u:fa[u]=find(fa[u]);
}
bool merge(int u,int v){
u=find(u),v=find(v);
if(u==v)return 0;
if(sz[u]<sz[v])swap(u,v);
fa[v]=u,sz[u]+=sz[v];
return 1;
}
}
struct node{
int a,c,A,C;
node():a(inf),A(inf){}
node(int _a,int _c,int _A,int _C):a(_a),c(_c),A(_A),C(_C){}
friend node operator+(node x,node y){
if(x.a>y.a)swap(x,y);
if(y.c!=x.c&&y.a<x.A)x.A=y.a,x.C=y.c;
else if(y.A<x.A)x.A=y.A,x.C=y.C;
return x;
}
pair<int,int> ask(int x){
return c==x?make_pair(A,C):make_pair(a,c);
}
};
int fa[N],ax[M],ay[M];
vector<int>e[N];
vector<pair<int,int>>bx[N],by[N];
int sz[N],hc[N];
void init(int u){
sz[u]=1;
for(int v:e[u]){
init(v),sz[u]+=sz[v];
if(sz[v]>sz[hc[u]])hc[u]=v;
}
}
int p[N],tot,rt,Fa[N],lc[N],rc[N],dfn[N],dn,top[N];
node f[N],g[N];
void pushup(int u){
f[u]=g[u];
if(lc[u])f[u]=f[lc[u]]+f[u];
if(rc[u])f[u]=f[u]+f[rc[u]];
}
int cbuild(int pl,int pr){
if(pl>pr)return 0;
int l=pl,r=pr,mid;
while(l<r){
mid=(l+r>>1)+1;
if(sz[p[pl]]-sz[p[mid]]<sz[p[mid]]-sz[hc[p[pr]]])l=mid;
else r=mid-1;
}
r=p[l],lc[r]=cbuild(pl,l-1),rc[r]=cbuild(l+1,pr),pushup(r);
return Fa[lc[r]]=Fa[rc[r]]=r;
}
int build(int u){
for(int i=u;i;i=hc[i]){
dfn[i]=++dn,top[i]=u;
for(int v:e[i])if(v!=hc[i])Fa[build(v)]=i;
}
tot=0;
for(int i=u;i;i=hc[i])p[++tot]=i;
return cbuild(1,tot);
}
void upd(int u){
pushup(u);
while(top[Fa[u]]==top[u])u=Fa[u],pushup(u);
}
node ask(int u){
node x=f[lc[u]]+g[u];
while(u){
int v=Fa[u];
if(u!=lc[v])x=x+f[lc[v]]+g[v];
u=v;
}
return x;
}
int ls[K],rs[K],cntnode;
node sum[K];
int newnode(){
cntnode++,ls[cntnode]=rs[cntnode]=0,sum[cntnode]=node();
return cntnode;
}
void upd(int u,int l,int r,int x,node y){
sum[u]=sum[u]+y;
if(l==r)return;
int mid=l+r>>1;
if(x<=mid)upd(ls[u]?ls[u]:ls[u]=newnode(),l,mid,x,y);
else upd(rs[u]?rs[u]:rs[u]=newnode(),mid+1,r,x,y);
}
node ask(int u,int l,int r,int x,int y){
if(x<=l&&r<=y)return sum[u];
int mid=l+r>>1;
if(ls[u]&&x<=mid&&rs[u]&&y>mid)return ask(ls[u],l,mid,x,y)+ask(rs[u],mid+1,r,x,y);
if(ls[u]&&x<=mid)return ask(ls[u],l,mid,x,y);
if(rs[u]&&y>mid)return ask(rs[u],mid+1,r,x,y);
return node();
}
void merge(int u,int v,int l,int r){
if(l==r){
sum[u]=sum[u]+sum[v];
return;
}
int mid=l+r>>1;
if(!ls[u])ls[u]=ls[v];
else if(ls[v])merge(ls[u],ls[v],l,mid);
if(!rs[u])rs[u]=rs[v];
else if(rs[v])merge(rs[u],rs[v],mid+1,r);
sum[u]=sum[ls[u]]+sum[rs[u]];
}
node t[N<<2];
int cntmemo;
pair<int,node>memo[K];
void modify(int u,int l,int r,int x,node y){
memo[++cntmemo]={u,t[u]},t[u]=t[u]+y;
if(l==r)return;
int mid=l+r>>1;
if(x<=mid)modify(u<<1,l,mid,x,y);
else modify(u<<1|1,mid+1,r,x,y);
}
node query(int u,int l,int r,int x,int y){
if(x<=l&&r<=y)return t[u];
int mid=l+r>>1;
if(x<=mid&&y>mid)return query(u<<1,l,mid,x,y)+query(u<<1|1,mid+1,r,x,y);
if(x<=mid)return query(u<<1,l,mid,x,y);
return query(u<<1|1,mid+1,r,x,y);
}
pair<int,int> Min[M];
node dfs1(int u,node x){
for(auto i:bx[u])x=x+(node){sz[i.first]+sz[u],dsu::find(i.second),inf,0};
for(auto i:bx[u]){
pair<int,int> w=x.ask(dsu::find(i.second));
w.first+=sz[i.first]-sz[u];
Min[i.second]=min(Min[i.second],w);
}
node res;
for(int v:e[u])res=res+dfs1(v,x);
for(auto i:bx[u])res=res+(node){sz[i.first]-sz[u],dsu::find(i.second),inf,0};
for(auto i:bx[u]){
pair<int,int> w=res.ask(dsu::find(i.second));
w.first+=sz[i.first]+sz[u];
Min[i.second]=min(Min[i.second],w);
}
return res;
}
node dfs2(int u,node x){
for(auto i:by[u])x=x+(node){sz[i.first]+sz[u],dsu::find(i.second),inf,0};
for(auto i:by[u]){
pair<int,int> w=x.ask(dsu::find(i.second));
w.first+=sz[i.first]-sz[u];
Min[i.second]=min(Min[i.second],w);
}
node res;
for(int v:e[u])res=res+dfs2(v,x);
for(auto i:by[u])res=res+(node){sz[i.first]-sz[u],dsu::find(i.second),inf,0};
for(auto i:by[u]){
pair<int,int> w=res.ask(dsu::find(i.second));
w.first+=sz[i.first]+sz[u];
Min[i.second]=min(Min[i.second],w);
}
return res;
}
vector<node>lstv[N];
void dfs3(int u){
for(int I=0;I<bx[u].size();I++){
auto i=bx[u][I];
lstv[u][I]=g[i.first];
g[i.first]=g[i.first]+(node){sz[u]+sz[i.first],dsu::find(i.second),inf,0};
upd(i.first);
}
for(auto i:bx[u]){
pair<int,int> w=ask(i.first).ask(dsu::find(i.second));
w.first+=-sz[u]-sz[i.first];
Min[i.second]=min(Min[i.second],w);
}
for(int v:e[u])dfs3(v);
for(int I=bx[u].size()-1;~I;I--){
auto i=bx[u][I];
g[i.first]=lstv[u][I];
upd(i.first);
}
}
void dfs4(int u){
for(int v:e[u])dfs4(v),merge(u,v,1,n);
for(auto i:bx[u]){
upd(u,1,n,dfn[i.first],(node){-sz[u]-sz[i.first],dsu::find(i.second),inf,0});
}
for(auto i:bx[u]){
pair<int,int> w=ask(u,1,n,dfn[i.first],dfn[i.first]+sz[i.first]-1).ask(dsu::find(i.second));
w.first+=sz[u]+sz[i.first];
Min[i.second]=min(Min[i.second],w);
}
}
void dfs5(int u){
int x=cntmemo;
for(auto i:bx[u]){
modify(1,1,n,dfn[i.first],(node){sz[u]-sz[i.first],dsu::find(i.second),inf,0});
}
for(auto i:bx[u]){
pair<int,int> w=query(1,1,n,dfn[i.first],dfn[i.first]+sz[i.first]-1).ask(dsu::find(i.second));
w.first+=sz[i.first]-sz[u];
Min[i.second]=min(Min[i.second],w);
}
for(int v:e[u])dfs5(v);
while(cntmemo>x)t[memo[cntmemo].first]=memo[cntmemo].second,cntmemo--;
}
void dfs6(int u){
int x=cntmemo;
for(auto i:by[u]){
modify(1,1,n,dfn[i.first],(node){sz[u]-sz[i.first],dsu::find(i.second),inf,0});
}
for(auto i:by[u]){
pair<int,int> w=query(1,1,n,dfn[i.first],dfn[i.first]+sz[i.first]-1).ask(dsu::find(i.second));
w.first+=sz[i.first]-sz[u];
Min[i.second]=min(Min[i.second],w);
}
for(int v:e[u])dfs6(v);
while(cntmemo>x)t[memo[cntmemo].first]=memo[cntmemo].second,cntmemo--;
}
int main(){
n=read(),m=read();
for(int i=2;i<=n;i++)fa[i]=read(),e[fa[i]].push_back(i);
for(int i=1;i<=m;i++){
ax[i]=read(),ay[i]=read();
bx[ax[i]].push_back({ay[i],i}),by[ay[i]].push_back({ax[i],i});
}
for(int i=1;i<=n;i++)lstv[i].resize(bx[i].size());
init(1),rt=build(1);
ll ans=0;
dsu::init();
while(dsu::sz[dsu::find(1)]!=m){
node x;
for(int i=1;i<=m;i++)x=x+(node){sz[ax[i]]+sz[ay[i]],dsu::find(i),inf,0};
for(int i=1;i<=m;i++)Min[i]=x.ask(dsu::find(i)),Min[i].first+=sz[ax[i]]+sz[ay[i]];
cntnode=0;
for(int i=1;i<=n;i++)newnode();
dfs1(1,node()),dfs2(1,node()),dfs3(1),dfs4(1),dfs5(1),dfs6(1);
// for(int i=1;i<=m;i++)printf("(%d %d)",Min[i].first,Min[i].second);
// printf("\n");
for(int i=1;i<=m;i++)Min[dsu::find(i)]=min(Min[dsu::find(i)],Min[i]);
for(int i=1;i<=m;i++){
if(i==dsu::find(i)&&dsu::merge(i,Min[i].second))ans+=Min[i].first;
}
}
printf("%lld",ans);
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 33ms
memory: 323704kb
Test #2:
score: 10
Accepted
time: 34ms
memory: 323628kb
Test #3:
score: 10
Accepted
time: 28ms
memory: 324508kb
Test #4:
score: 10
Accepted
time: 26ms
memory: 324728kb
Test #5:
score: 10
Accepted
time: 31ms
memory: 323876kb
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 10
Accepted
time: 3225ms
memory: 377796kb
Test #7:
score: 10
Accepted
time: 2454ms
memory: 374992kb
Test #8:
score: 10
Accepted
time: 1241ms
memory: 370476kb
Test #9:
score: 10
Accepted
time: 1415ms
memory: 373348kb
Test #10:
score: 10
Accepted
time: 2018ms
memory: 373868kb
Subtask #3:
score: 10
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 10
Accepted
time: 4406ms
memory: 385460kb
Test #12:
score: 10
Accepted
time: 2803ms
memory: 382508kb
Test #13:
score: 10
Accepted
time: 1523ms
memory: 374172kb
Test #14:
score: 10
Accepted
time: 1668ms
memory: 378736kb
Test #15:
score: 10
Accepted
time: 2372ms
memory: 379488kb
Subtask #4:
score: 20
Accepted
Test #16:
score: 20
Accepted
time: 268ms
memory: 330360kb
Test #17:
score: 20
Accepted
time: 318ms
memory: 332008kb
Test #18:
score: 20
Accepted
time: 209ms
memory: 330332kb
Test #19:
score: 20
Accepted
time: 233ms
memory: 329196kb
Test #20:
score: 20
Accepted
time: 259ms
memory: 330048kb
Subtask #5:
score: 10
Accepted
Test #21:
score: 10
Accepted
time: 7023ms
memory: 584008kb
Test #22:
score: 10
Accepted
time: 7080ms
memory: 584952kb
Test #23:
score: 10
Accepted
time: 7213ms
memory: 586988kb
Test #24:
score: 10
Accepted
time: 7095ms
memory: 587000kb
Test #25:
score: 10
Accepted
time: 6921ms
memory: 586872kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 923ms
memory: 374024kb
Test #27:
score: 10
Accepted
time: 865ms
memory: 373900kb
Test #28:
score: 10
Accepted
time: 896ms
memory: 374020kb
Test #29:
score: 10
Accepted
time: 904ms
memory: 376068kb
Test #30:
score: 10
Accepted
time: 861ms
memory: 374024kb
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: 6152ms
memory: 393024kb
Test #32:
score: 30
Accepted
time: 4326ms
memory: 392500kb
Test #33:
score: 30
Accepted
time: 1916ms
memory: 384760kb
Test #34:
score: 30
Accepted
time: 2096ms
memory: 391496kb
Test #35:
score: 30
Accepted
time: 2776ms
memory: 388820kb
Test #36:
score: 30
Accepted
time: 5340ms
memory: 394072kb
Test #37:
score: 30
Accepted
time: 4401ms
memory: 392108kb
Test #38:
score: 30
Accepted
time: 1915ms
memory: 386580kb
Test #39:
score: 30
Accepted
time: 2101ms
memory: 390944kb
Test #40:
score: 30
Accepted
time: 2784ms
memory: 388656kb