QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#885609#4408. 燃烧的呐球cqbzxzj100 ✓7213ms587000kbC++147.2kb2025-02-06 16:34:292025-02-06 16:34:30

Judging History

This is the latest submission verdict.

  • [2025-02-06 16:34:30]
  • Judged
  • Verdict: 100
  • Time: 7213ms
  • Memory: 587000kb
  • [2025-02-06 16:34:29]
  • Submitted

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