QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#887659#4408. 燃烧的呐球cqbztzl100 ✓8437ms1176392kbC++1410.9kb2025-02-07 18:57:152025-02-07 18:57:16

Judging History

This is the latest submission verdict.

  • [2025-02-07 18:57:16]
  • Judged
  • Verdict: 100
  • Time: 8437ms
  • Memory: 1176392kb
  • [2025-02-07 18:57:15]
  • Submitted

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp(a,b) make_pair(a,b)	
#define ull unsigned long long
using namespace std;
int n,m,tot,w[1000005],fa[100005],len[1000005],f[1000005],son[1000005],dfn[1000005],Dfn[1000005];
long long ans;
vector<int>g[1000005];
struct node{
	int x,y;
}a[100005];
inline int find(int x){
	if(fa[x]==x)return x;
	else return fa[x]=find(fa[x]);
}
void dfs(int x,int fa){
	w[x]=1;
	len[x]=len[fa]+1;
	dfn[x]=++tot;
	Dfn[tot]=x;
	for(int v:g[x]){
		dfs(v,x);
		w[x]+=w[v];
		if(w[son[x]]<w[v])son[x]=v;
	}
}
int res[100005],to[100005];
struct Val{
	int minn,idm,oth,ido;
	inline Val(){minn=oth=1e8,idm=ido=-1;}
	inline Val(int minn,int idm,int oth=1e8,int ido=-1):minn(minn),idm(idm),oth(oth),ido(ido){}
};
int col[100005];
inline Val Merge(Val x,Val y){
	if(x.idm==-1)return y;
	if(y.idm==-1)return x;
	Val z;
	if(x.minn>y.minn)swap(x,y);
	z.minn=x.minn;
	z.idm=x.idm;
	if(col[x.idm]!=col[y.idm]){
		z.oth=min(x.oth,y.minn);
		if(z.oth==x.oth)z.ido=x.ido;
		else z.ido=y.idm;
	}
	else{
		z.oth=min(x.oth,y.oth);
		if(z.oth==x.oth)z.ido=x.ido;
		else z.ido=y.ido;
	}
//	cerr<<x.minn<<" "<<x.idm<<' '<<x.oth<<' '<<x.ido<<" "<<y.minn<<" "<<y.idm<<' '<<y.oth<<' '<<y.ido<<" "<<z.minn<<" "<<z.idm<<' '<<z.oth<<' '<<z.ido<<endl;
	return z;
}
struct ST{
	int rt[1000005],cnt;
	void clear(){
		for(int i=1;i<=n;i++)rt[i]=0;
		cnt=0;
		c[0].minn=Val();
	}
	struct Node{
		int son[2];
		Val minn;
	}c[10000005];
	int New(){
		cnt++;
		c[cnt].son[0]=c[cnt].son[1]=0;
		c[cnt].minn=Val();
		return cnt;
	}
	void Add(int &q,int L,int R,int x,Val y){
		if(!q)q=New();
		if(L==R){
			c[q].minn=Merge(c[q].minn,y);
			return;
		}
		int mid=L+R>>1;
		if(x<=mid)Add(c[q].son[0],L,mid,x,y);
		else Add(c[q].son[1],mid+1,R,x,y);
		c[q].minn=Merge(c[c[q].son[0]].minn,c[c[q].son[1]].minn);
	}
	Val Get(int q,int L,int R,int l,int r){
//		cerr<<q<<" "<<L<<" "<<R<<' '<<l<<' '<<r<<endl;
		if(!q)return Val();
		if(l<=L&&R<=r)return c[q].minn;
		int mid=L+R>>1;
		if(r<=mid)return Get(c[q].son[0],L,mid,l,r);
		if(mid<l)return Get(c[q].son[1],mid+1,R,l,r);
		return Merge(Get(c[q].son[0],L,mid,l,r),Get(c[q].son[1],mid+1,R,l,r));
	}
	int Merget(int q1,int q2,int L,int R){
		if(!q1||!q2)return q1+q2;
		c[q1].minn=Merge(c[q1].minn,c[q2].minn);
		if(L==R)return q1;
		int mid=L+R>>1;
		c[q1].son[0]=Merget(c[q1].son[0],c[q2].son[0],L,mid);
		c[q1].son[1]=Merget(c[q1].son[1],c[q2].son[1],mid+1,R);
		return q1;
	}
	void dfs(int q,int L,int R){
		if(!q)return;
		if(L==R){
			cerr<<q<<' '<<L<<" "<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
			return;
		}
			cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
		int mid=L+R>>1;
		dfs(c[q].son[0],L,mid);
		dfs(c[q].son[1],mid+1,R);
	}
};
struct ST1{
	int rt[1000005],cnt;
	void clear(){
		for(int i=1;i<=n;i++)rt[i]=0;
		cnt=0;
		c[0].minn=Val();
	}
	struct Node{
		int son[2];
		Val minn;
	}c[10000005];
	int New(int q){
		cnt++;
		c[cnt]=c[q];
		return cnt;
	}
	void Add(int &q,int L,int R,int x,Val y){
		q=New(q);
		if(L==R){
			c[q].minn=Merge(c[q].minn,y);
			return;
		}
		int mid=L+R>>1;
		if(x<=mid)Add(c[q].son[0],L,mid,x,y);
		else Add(c[q].son[1],mid+1,R,x,y);
		c[q].minn=Merge(c[c[q].son[0]].minn,c[c[q].son[1]].minn);
	}
	Val Get(int q,int L,int R,int l,int r){
		if(!q)return Val();
		if(l<=L&&R<=r)return c[q].minn;
		int mid=L+R>>1;
		if(r<=mid)return Get(c[q].son[0],L,mid,l,r);
		if(mid<l)return Get(c[q].son[1],mid+1,R,l,r);
		return Merge(Get(c[q].son[0],L,mid,l,r),Get(c[q].son[1],mid+1,R,l,r));
	}
	void dfs(int q,int L,int R){
		if(!q)return;
		if(L==R){
			cerr<<q<<' '<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
			return;
		}
		int mid=L+R>>1;
		dfs(c[q].son[0],L,mid);
		dfs(c[q].son[1],mid+1,R);
			cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
	}
};
vector<int>posx[1000005],posy[1000005];
namespace S1{
	Val x[1000005];
	void dfs1(int u){
		x[u]=Val();
		for(int p:posy[u]){
			x[u]=Merge(x[u],Val(w[a[p].x]-w[a[p].y],p));
		}
		for(int v:g[u]){
			dfs1(v);
			x[u]=Merge(x[u],x[v]);
		}
		for(int p:posy[u]){
			int v,t;
			if(col[p]==col[x[u].idm]){
				v=w[a[p].x]+w[a[p].y]+x[u].oth;
				t=x[u].ido;
			}
			else{
				v=w[a[p].x]+w[a[p].y]+x[u].minn;
				t=x[u].idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
	}
	void dfs2(int u){
		x[u]=Val();
		for(int p:posx[u]){
			x[u]=Merge(x[u],Val(-w[a[p].x]+w[a[p].y],p));
		}
		for(int v:g[u]){
			dfs2(v);
			x[u]=Merge(x[u],x[v]);
		}
		for(int p:posx[u]){
			int v,t;
			if(col[p]==col[x[u].idm]){
				v=w[a[p].x]+w[a[p].y]+x[u].oth;
				t=x[u].ido;
			}
			else{
				v=w[a[p].x]+w[a[p].y]+x[u].minn;
				t=x[u].idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
	}
	void dfs3(int u,Val tag){
		for(int p:posx[u]){
			tag=Merge(tag,Val(w[a[p].x]+w[a[p].y],p));
		}
		for(int p:posx[u]){
			int v,t;
			if(col[p]==col[tag.idm]){
				v=-w[a[p].x]+w[a[p].y]+tag.oth;
				t=tag.ido;
			}
			else{
				v=-w[a[p].x]+w[a[p].y]+tag.minn;
				t=tag.idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
		for(int v:g[u]){
			dfs3(v,tag);
		}
	}
	void dfs4(int u,Val tag){
		for(int p:posy[u]){
			tag=Merge(tag,Val(w[a[p].x]+w[a[p].y],p));
		}
		for(int p:posy[u]){
			int v,t;
			if(col[p]==col[tag.idm]){
				v=w[a[p].x]-w[a[p].y]+tag.oth;
				t=tag.ido;
			}
			else{
				v=w[a[p].x]-w[a[p].y]+tag.minn;
				t=tag.idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
		for(int v:g[u]){
			dfs4(v,tag);
		}
	}
	void init(){
		for(int i=1;i<=m;i++)x[i]=Val(w[a[i].x]+w[a[i].y],i);
		Val minn;
		for(int i=1;i<=m;i++)minn=Merge(minn,x[i]);
//		cerr<<minn.minn<<' '<<minn.idm<<' '<<minn.oth<<' '<<minn.ido<<endl;
		for(int i=1;i<=m;i++){
			int v,t;
			if(col[i]==col[minn.idm]){
				v=w[a[i].x]+w[a[i].y]+minn.oth;
				t=minn.ido;
			}
			else{
				v=w[a[i].x]+w[a[i].y]+minn.minn;
				t=minn.idm;
			}
			if(v<res[i]){
				res[i]=v;
				to[i]=t;
			}
		}
		dfs1(1);
		dfs2(1);
		dfs3(1,Val());
		dfs4(1,Val());
	}
}
namespace S2{
	ST T;
	void dfs(int u){
		for(int p:posx[u]){
//			cerr<<u<<":"<<p<<endl;
			T.Add(T.rt[u],1,n,dfn[a[p].y],Val(-w[a[p].x]-w[a[p].y],p));
		}
		for(int v:g[u]){
			dfs(v);
			T.rt[u]=T.Merget(T.rt[u],T.rt[v],1,n);
		}
//		cerr<<u<<"::"<<endl;
//		T.dfs(T.rt[u],1,n);cerr<<endl;
		for(int p:posx[u]){
			int v,t;
			Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1);
//			cerr<<p<<" "<<minn.minn<<" "<<minn.idm<<" "<<minn.oth<<" "<<minn.ido<<endl;
			if(col[p]==col[minn.idm]){
				v=w[a[p].x]+w[a[p].y]+minn.oth;
				t=minn.ido;
			}
			else{
				v=w[a[p].x]+w[a[p].y]+minn.minn;
				t=minn.idm;
			}
//			cerr<<"="<<p<<' '<<v<<" "<<t<<endl;
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
	}
	void init(){
		T.clear();
		dfs(1);
	}
}
namespace S3{
	ST1 T;
	void dfs1(int u){
		for(int p:posx[u]){
			T.Add(T.rt[u],1,n,dfn[a[p].y],Val(w[a[p].x]-w[a[p].y],p));
		}
		for(int p:posx[u]){
			int v,t;
			Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1);
			if(col[p]==col[minn.idm]){
				v=-w[a[p].x]+w[a[p].y]+minn.oth;
				t=minn.ido;
			}
			else{
				v=-w[a[p].x]+w[a[p].y]+minn.minn;
				t=minn.idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
		for(int v:g[u]){
			T.rt[v]=T.rt[u];
			dfs1(v);
		}
	}
	void dfs2(int u){
		for(int p:posy[u]){
			T.Add(T.rt[u],1,n,dfn[a[p].x],Val(-w[a[p].x]+w[a[p].y],p));
		}
		for(int p:posy[u]){
			int v,t;
			Val minn=T.Get(T.rt[u],1,n,dfn[a[p].x],dfn[a[p].x]+w[a[p].x]-1);
			if(col[p]==col[minn.idm]){
				v=w[a[p].x]-w[a[p].y]+minn.oth;
				t=minn.ido;
			}
			else{
				v=w[a[p].x]-w[a[p].y]+minn.minn;
				t=minn.idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
		for(int v:g[u]){
			T.rt[v]=T.rt[u];
			dfs2(v);
		}
	}
	void init(){
		T.clear();
		dfs1(1);
		T.clear();
		dfs2(1);
	}
}
struct ST2{
	int rt[1000005],cnt;
	void clear(){
		for(int i=1;i<=n;i++)rt[i]=0;
		cnt=0;
		c[0].minn=Val();
	}
	struct Node{
		int son[2];
		Val minn;
	}c[10000005];
	inline int New(int q){
		cnt++;
		c[cnt]=c[q];
		return cnt;
	}
	void Add(int &q,int L,int R,int l,int r,Val x){
		q=New(q);
		if(l<=L&&R<=r){
			c[q].minn=Merge(c[q].minn,x);
			return;
		}
		int mid=L+R>>1;
		if(l<=mid)Add(c[q].son[0],L,mid,l,r,x);
		if(mid<r)Add(c[q].son[1],mid+1,R,l,r,x);
	}
	Val Get(int q,int L,int R,int x){
		if(!q)return Val();
		if(L==R)return c[q].minn;
		int mid=L+R>>1;
		if(x<=mid)return Merge(c[q].minn,Get(c[q].son[0],L,mid,x));
		else return Merge(c[q].minn,Get(c[q].son[1],mid+1,R,x));
	}
	void dfs(int q,int L,int R){
		if(!q)return;
		if(L==R){
			cerr<<q<<' '<<L<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
			return;
		}
		int mid=L+R>>1;
		dfs(c[q].son[0],L,mid);
		dfs(c[q].son[1],mid+1,R);
			cerr<<q<<" "<<L<<' '<<R<<' '<<c[q].minn.minn<<" "<<c[q].minn.idm<<' '<<c[q].minn.oth<<' '<<c[q].minn.ido<<endl;
	}
};
namespace S4{
	ST2 T;
	void dfs(int u){
		for(int p:posx[u]){
			T.Add(T.rt[u],1,n,dfn[a[p].y],dfn[a[p].y]+w[a[p].y]-1,Val(w[a[p].x]+w[a[p].y],p));
		}
		for(int p:posx[u]){
			int v,t;
			Val minn=T.Get(T.rt[u],1,n,dfn[a[p].y]);
			if(col[p]==col[minn.idm]){
				v=-w[a[p].x]-w[a[p].y]+minn.oth;
				t=minn.ido;
			}
			else{
				v=-w[a[p].x]-w[a[p].y]+minn.minn;
				t=minn.idm;
			}
			if(v<res[p]){
				res[p]=v;
				to[p]=t;
			}
		}
		for(int v:g[u]){
			T.rt[v]=T.rt[u];
			dfs(v);
		}
	}
	void init(){
		T.clear();
		dfs(1);
	}
}
signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=2,x;i<=n;i++)scanf("%d",&x),g[x].push_back(i);
	for(int i=1;i<=m;i++)scanf("%d%d",&a[i].x,&a[i].y),posx[a[i].x].push_back(i),posy[a[i].y].push_back(i);
	for(int i=1;i<=m;i++)fa[i]=i;
	dfs(1,0);
	int k=m-1;
	S1::init();
	while(k){
		for(int i=1;i<=m;i++){
			res[i]=1e8,to[i]=-1;
		}
		for(int i=1;i<=m;i++)col[i]=find(i);
		S1::init();
		S2::init();
		S3::init();
		S4::init();
//		cerr<<"AS"<<endl;
//		cerr<<ans<<endl;
//		for(int i=1;i<=m;i++)cerr<<find(i)<<' ';cerr<<endl;
//		for(int i=1;i<=m;i++)cerr<<res[i]<<' ';cerr<<endl;
//		for(int i=1;i<=m;i++)cerr<<to[i]<<' ';cerr<<endl;
		for(int i=1;i<=m;i++){
			int p=find(i);
			if(i!=p){
				if(res[i]<res[p]){
					res[p]=res[i];
					to[p]=to[i];
				}
			}
		}
		for(int i=1;i<=m;i++){
//			cerr<<i<<' '<<fa[i]<<" "<<find(i)<<" "<<res[i]<<' '<<to[i]<<endl;
			if(fa[i]==i){
				if(find(i)!=find(to[i])){
					k--;
					ans+=res[i];
					int v=find(to[i]);
					fa[i]=v;
				}
			}
		}
//		cerr<<k<<endl;
	}
	printf("%lld",ans);
	return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 52ms
memory: 804744kb

Test #2:

score: 10
Accepted
time: 44ms
memory: 804752kb

Test #3:

score: 10
Accepted
time: 53ms
memory: 804880kb

Test #4:

score: 10
Accepted
time: 49ms
memory: 804876kb

Test #5:

score: 10
Accepted
time: 47ms
memory: 808844kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 4428ms
memory: 848824kb

Test #7:

score: 10
Accepted
time: 2569ms
memory: 846292kb

Test #8:

score: 10
Accepted
time: 1251ms
memory: 840088kb

Test #9:

score: 10
Accepted
time: 1367ms
memory: 845060kb

Test #10:

score: 10
Accepted
time: 2008ms
memory: 843976kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 5743ms
memory: 850696kb

Test #12:

score: 10
Accepted
time: 3753ms
memory: 848096kb

Test #13:

score: 10
Accepted
time: 1942ms
memory: 841772kb

Test #14:

score: 10
Accepted
time: 2217ms
memory: 846916kb

Test #15:

score: 10
Accepted
time: 3039ms
memory: 845908kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 321ms
memory: 808056kb

Test #17:

score: 20
Accepted
time: 359ms
memory: 808060kb

Test #18:

score: 20
Accepted
time: 237ms
memory: 808060kb

Test #19:

score: 20
Accepted
time: 285ms
memory: 806144kb

Test #20:

score: 20
Accepted
time: 314ms
memory: 806136kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 8001ms
memory: 1176156kb

Test #22:

score: 10
Accepted
time: 8102ms
memory: 1176392kb

Test #23:

score: 10
Accepted
time: 8437ms
memory: 1176392kb

Test #24:

score: 10
Accepted
time: 8339ms
memory: 1176260kb

Test #25:

score: 10
Accepted
time: 7887ms
memory: 1176148kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1183ms
memory: 832328kb

Test #27:

score: 10
Accepted
time: 1156ms
memory: 832168kb

Test #28:

score: 10
Accepted
time: 1160ms
memory: 832452kb

Test #29:

score: 10
Accepted
time: 1146ms
memory: 832216kb

Test #30:

score: 10
Accepted
time: 1242ms
memory: 832320kb

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: 6721ms
memory: 853736kb

Test #32:

score: 30
Accepted
time: 4324ms
memory: 851012kb

Test #33:

score: 30
Accepted
time: 2467ms
memory: 844648kb

Test #34:

score: 30
Accepted
time: 2665ms
memory: 849860kb

Test #35:

score: 30
Accepted
time: 3524ms
memory: 848688kb

Test #36:

score: 30
Accepted
time: 6804ms
memory: 853564kb

Test #37:

score: 30
Accepted
time: 4434ms
memory: 850948kb

Test #38:

score: 30
Accepted
time: 2513ms
memory: 844648kb

Test #39:

score: 30
Accepted
time: 2726ms
memory: 849860kb

Test #40:

score: 30
Accepted
time: 3725ms
memory: 848824kb