QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#884447 | #4408. 燃烧的呐球 | cqbzxzj | 10 | 7481ms | 570464kb | C++14 | 7.0kb | 2025-02-06 08:23:15 | 2025-02-06 08:23:16 |
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;
while(u){
int v=Fa[u];
if(u==rc[v])x=x+f[lc[v]];
x=x+g[u],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=x.ask(dsu::find(i.second));
w.first+=sz[i.first]+sz[u];
}
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=x.ask(dsu::find(i.second));
w.first+=sz[i.first]+sz[u];
}
return res;
}
vector<node>lstv[N];
void dfs3(int u){
lstv[u].resize(bx[u].size());
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=0;I<bx[u].size();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});
}
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 32ms
memory: 326936kb
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 255ms
memory: 329556kb
Subtask #5:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 7481ms
memory: 570464kb
Subtask #6:
score: 10
Accepted
Test #26:
score: 10
Accepted
time: 1030ms
memory: 374024kb
Test #27:
score: 10
Accepted
time: 1044ms
memory: 374028kb
Test #28:
score: 10
Accepted
time: 1018ms
memory: 373888kb
Test #29:
score: 10
Accepted
time: 1037ms
memory: 376068kb
Test #30:
score: 10
Accepted
time: 1021ms
memory: 374024kb
Subtask #7:
score: 0
Skipped
Dependency #1:
0%