QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557421#4408. 燃烧的呐球DaiRuiChen007100 ✓4426ms606828kbC++176.9kb2024-09-11 09:36:572024-09-11 09:36:57

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 09:36:57]
  • 评测
  • 测评结果:100
  • 用时:4426ms
  • 内存:606828kb
  • [2024-09-11 09:36:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5,MAXM=1e5+5,inf=1e9;
vector <int> G[MAXN],qx[MAXN],qy[MAXN];
int fa[MAXN],siz[MAXN],id[MAXN],dcnt,L[MAXN],R[MAXN];
int n,m,col[MAXN],X[MAXN],Y[MAXN];
vector <int> dfn,rdfn,eul;
long long ans=0;
inline void dfs(int u) {
	L[u]=id[u]=++dcnt,siz[u]=1;
	dfn.push_back(u),eul.push_back(u);
	for(int v:G[u]) dfs(v),siz[u]+=siz[v];
	R[u]=dcnt;
	rdfn.push_back(u),eul.push_back(-u);
}
struct E {
	int v,w;
	E(int x=0,int c=inf): v(x),w(c) {}
	inline friend bool operator==(E x,E y) { return x.v==y.v; }
	inline friend bool operator <(E x,E y) { return x.w<y.w; }
};
struct I {
	E mn1,mn2;
	I(int x=0,int c=inf): mn1(x,c),mn2(0,inf) {}
	inline I operator +=(I oth) {
		if(oth.mn1<mn1) swap(oth.mn1,mn1),swap(oth.mn2,mn2);
		mn2=min(mn2,oth.mn1==mn1?oth.mn2:oth.mn1);
		return *this;
	}
	inline I operator +=(int oth) {
		mn1.w+=oth,mn2.w+=oth;
		return *this;
	}
	inline I operator +(I oth) const {
		I tmp(*this);
		return tmp+=oth;
	}
	inline I operator +(int oth) const {
		I tmp(*this);
		return tmp+=oth;
	}
};
struct D {
	int id;
	I val;
	D(int i=0,I v=I()): id(i),val(v) {}
};
I r[MAXN];
namespace Case1 { //out,out
inline void main() {
	I now;
	for(int i=1;i<=m;++i) now+=I(col[i],siz[X[i]]+siz[Y[i]]);
	for(int i=1;i<=m;++i) r[i]+=now+(siz[X[i]]+siz[Y[i]]);
}
}
namespace Case2 { //son,out
I minx[MAXN],miny[MAXN];
inline void main() {
	for(int i=1;i<=n;++i) minx[i]=miny[i]=I();
	for(int u:rdfn) {
		for(int i:qx[u]) minx[u]+=I(col[i],siz[Y[i]]-siz[X[i]]);
		for(int i:qy[u]) miny[u]+=I(col[i],siz[X[i]]-siz[Y[i]]);
		for(int v:G[u]) minx[u]+=minx[v],miny[u]+=miny[v];
		for(int i:qx[u]) r[i]+=minx[u]+(siz[Y[i]]+siz[X[i]]);
		for(int i:qy[u]) r[i]+=miny[u]+(siz[X[i]]+siz[Y[i]]);
	}
}
}
namespace Case3 { //fa,out
I minx[MAXN],miny[MAXN];
inline void main() {
	for(int i=1;i<=n;++i) minx[i]=I(),miny[i]=I();
	for(int u:dfn) {
		for(int i:qx[u]) minx[u]+=I(col[i],siz[X[i]]+siz[Y[i]]);
		for(int i:qy[u]) miny[u]+=I(col[i],siz[Y[i]]+siz[X[i]]);
		for(int v:G[u]) minx[v]+=minx[u],miny[v]+=miny[u];
		for(int i:qx[u]) r[i]+=minx[u]+(siz[Y[i]]-siz[X[i]]);
		for(int i:qy[u]) r[i]+=miny[u]+(siz[X[i]]-siz[Y[i]]);
	}
}
}
namespace Case4 { //son son
struct SegmentTree {
	struct Node {
		int ls,rs;
		I min;
	}	tr[MAXM*24];
	int tot;
	inline void ins(int u,I k,int l,int r,int &p) {
		if(!p) tr[p=++tot]={0,0,I()}; tr[p].min+=k;
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(u<=mid) ins(u,k,l,mid,tr[p].ls);
		else ins(u,k,mid+1,r,tr[p].rs);
	}
	inline I qry(int ul,int ur,int l,int r,int p) {
		if(!p||ul>ur) return I();
		if(ul<=l&&r<=ur) return tr[p].min;
		int mid=(l+r)>>1;
		if(ur<=mid) return qry(ul,ur,l,mid,tr[p].ls);
		if(mid<ul) return qry(ul,ur,mid+1,r,tr[p].rs);
		return qry(ul,ur,l,mid,tr[p].ls)+qry(ul,ur,mid+1,r,tr[p].rs);
	}
	inline void merge(int l,int r,int q,int &p) {
		if(!p||!q) return p+=q,void();
		tr[p].min+=tr[q].min;
		if(l==r) return ;
		int mid=(l+r)>>1;
		merge(l,mid,tr[q].ls,tr[p].ls),merge(mid+1,r,tr[q].rs,tr[p].rs);
	}
}	T;
int rt[MAXN];
inline void main() {
	T.tot=0;
	for(int i=1;i<=n;++i) rt[i]=0;
	for(int u:rdfn) {
		for(int i:qx[u]) T.ins(id[Y[i]],I(col[i],-siz[X[i]]-siz[Y[i]]),1,n,rt[u]);
		for(int v:G[u])  T.merge(1,n,rt[v],rt[u]);
		for(int i:qx[u]) r[i]+=T.qry(L[Y[i]],R[Y[i]],1,n,rt[u])+(siz[X[i]]+siz[Y[i]]);
	}
}
}
namespace Case5 { //fa,son
D stk[MAXM*24];
int tp;
struct SegmentTree {
	static const int N=1<<20;
	I tr[N<<1];
	inline void upd(int x,I z) {
		x+=N,stk[++tp]=D(x,tr[x]),tr[x]+=z;
		for(x>>=1;x;x>>=1) stk[++tp]=D(x,tr[x]),tr[x]+=z;
	}
	inline I qry(int l,int r) {
		I g=I();
		for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) {
			if(!(l&1)) g+=tr[l^1];
			if(r&1) g+=tr[r^1];
		}
		return g;
	}
}	T;
int lst[MAXN];
inline void main() {
	for(int u:eul) {
		if(u>0) {
			lst[u]=tp;
			for(int i:qx[u]) T.upd(id[Y[i]],I(col[i],siz[X[i]]-siz[Y[i]]));
			for(int i:qx[u]) r[i]+=T.qry(L[Y[i]],R[Y[i]])+(siz[Y[i]]-siz[X[i]]);
		} else {
			u*=-1;
			while(tp>lst[u]) T.tr[stk[tp].id]=stk[tp].val,--tp;
		}
	}
	for(int u:eul) {
		if(u>0) {
			lst[u]=tp;
			for(int i:qy[u]) T.upd(id[X[i]],I(col[i],siz[Y[i]]-siz[X[i]]));
			for(int i:qy[u]) r[i]+=T.qry(L[X[i]],R[X[i]])+(siz[X[i]]-siz[Y[i]]);
		} else {
			u*=-1;
			while(tp>lst[u]) T.tr[stk[tp].id]=stk[tp].val,--tp;
		}
	}
}
}
namespace Case6 { //fa,fa
int hson[MAXN],top[MAXN];
inline void dfs(int u,int rt) {
	top[u]=rt;
	for(int v:G[u]) if(siz[v]>siz[hson[u]]) hson[u]=v;
	if(hson[u]) dfs(hson[u],rt);
	for(int v:G[u]) if(v^hson[u]) dfs(v,v);
}
D stk1[MAXM*24],stk2[MAXM];
int tp1,tp2;
struct BalanceTree {
	int ls[MAXN],rs[MAXN],f[MAXN];
	I w[MAXN],mx[MAXN];
	inline void build() {
		for(int s=1;s<=n;++s) if(top[s]==s) {
			vector <int> ci;
			for(int u=s;u;u=hson[u]) ci.push_back(u);
			function<int(int,int)> link=[&](int x,int y) {
				if(x>y) return 0;
				int all=0,tsiz=0;
				for(int i=x;i<=y;++i) all+=siz[ci[i]]-siz[hson[ci[i]]];
				for(int i=x;i<=y;++i) {
					tsiz+=siz[ci[i]]-siz[hson[ci[i]]];
					if(tsiz>all/2) {
						int p=ci[i];
						ls[p]=link(x,i-1),rs[p]=link(i+1,y);
						if(ls[p]) f[ls[p]]=p;
						if(rs[p]) f[rs[p]]=p;
						return p;
					}
				}
				return -1;
			};
			f[link(0,ci.size()-1)]=fa[s];
		}
	}
	inline void upd(int x,I z) {
		stk2[++tp2]=D(x,w[x]),w[x]+=z;
		for(;x;x=f[x]) {
			stk1[++tp1]=D(x,mx[x]),mx[x]+=z;
			if(x!=ls[f[x]]&&x!=rs[f[x]]) break;
		}
	}
	inline I qry(int x) {
		I g=w[x]+mx[ls[x]];
		for(;f[x];x=f[x]) if(x!=ls[f[x]]) g+=w[f[x]]+mx[ls[f[x]]];
		return g;
	}
}	T;
inline void init() { dfs(1,1),T.build(); }
int lst1[MAXN],lst2[MAXN];
inline void main() {
	for(int u:eul) {
		if(u>0) {
			lst1[u]=tp1,lst2[u]=tp2;;
			for(int i:qx[u]) T.upd(Y[i],I(col[i],siz[X[i]]+siz[Y[i]]));
			for(int i:qx[u]) r[i]+=T.qry(Y[i])+(-siz[X[i]]-siz[Y[i]]);
		} else {
			u*=-1;
			while(tp1>lst1[u]) T.mx[stk1[tp1].id]=stk1[tp1].val,--tp1;
			while(tp2>lst2[u]) T.w[stk2[tp2].id]=stk2[tp2].val,--tp2;
		}
	}
}
}
inline int find(int x) { while(x^col[x]) x=col[x]=col[col[x]]; return x; }
inline void boruvka() {
	for(int i=1;i<=m;++i) r[i]=I();
	Case1::main(),Case2::main(),Case3::main();
	Case4::main(),Case5::main(),Case6::main();
	vector <array<int,3>> cur;
	for(int i=1;i<=m;++i) if(i^col[i]) r[col[i]]+=r[i];
	for(int i=1;i<=m;++i) if(i==col[i]) {
		E e=(r[i].mn1.v==col[i])?r[i].mn2:r[i].mn1;
		cur.push_back({i,e.v,e.w});
	}
	for(auto i:cur) if(find(i[0])^find(i[1])) col[find(i[0])]=find(i[1]),ans+=i[2];
}
inline bool judge() {
	int cnt=0;
	for(int i=1;i<=m;++i) col[i]=find(i),cnt+=(i==col[i]);
	return cnt>1;
}
signed main() {
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;++i) scanf("%d",&fa[i]),G[fa[i]].push_back(i);
	dfs(1);
	Case6::init();
	for(int i=1;i<=m;++i) {
		scanf("%d%d",&X[i],&Y[i]),col[i]=i;
		qx[X[i]].push_back(i);
		qy[Y[i]].push_back(i);
	}
	while(judge()) boruvka();
	printf("%lld\n",ans);
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 31ms
memory: 371224kb

Test #2:

score: 10
Accepted
time: 28ms
memory: 377108kb

Test #3:

score: 10
Accepted
time: 23ms
memory: 380592kb

Test #4:

score: 10
Accepted
time: 28ms
memory: 382864kb

Test #5:

score: 10
Accepted
time: 24ms
memory: 374660kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 1751ms
memory: 463392kb

Test #7:

score: 10
Accepted
time: 1193ms
memory: 461168kb

Test #8:

score: 10
Accepted
time: 803ms
memory: 455808kb

Test #9:

score: 10
Accepted
time: 794ms
memory: 459828kb

Test #10:

score: 10
Accepted
time: 1180ms
memory: 459872kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 2649ms
memory: 465104kb

Test #12:

score: 10
Accepted
time: 1868ms
memory: 462828kb

Test #13:

score: 10
Accepted
time: 1285ms
memory: 457088kb

Test #14:

score: 10
Accepted
time: 1309ms
memory: 461472kb

Test #15:

score: 10
Accepted
time: 1748ms
memory: 460708kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 185ms
memory: 385280kb

Test #17:

score: 20
Accepted
time: 216ms
memory: 380248kb

Test #18:

score: 20
Accepted
time: 134ms
memory: 382680kb

Test #19:

score: 20
Accepted
time: 174ms
memory: 383724kb

Test #20:

score: 20
Accepted
time: 175ms
memory: 382532kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 4426ms
memory: 597364kb

Test #22:

score: 10
Accepted
time: 4125ms
memory: 599284kb

Test #23:

score: 10
Accepted
time: 4080ms
memory: 606828kb

Test #24:

score: 10
Accepted
time: 4044ms
memory: 600884kb

Test #25:

score: 10
Accepted
time: 4079ms
memory: 598860kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 994ms
memory: 458508kb

Test #27:

score: 10
Accepted
time: 977ms
memory: 456420kb

Test #28:

score: 10
Accepted
time: 981ms
memory: 456744kb

Test #29:

score: 10
Accepted
time: 990ms
memory: 454260kb

Test #30:

score: 10
Accepted
time: 977ms
memory: 452168kb

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: 3459ms
memory: 478484kb

Test #32:

score: 30
Accepted
time: 2267ms
memory: 470644kb

Test #33:

score: 30
Accepted
time: 1576ms
memory: 464576kb

Test #34:

score: 30
Accepted
time: 1621ms
memory: 469252kb

Test #35:

score: 30
Accepted
time: 2117ms
memory: 468768kb

Test #36:

score: 30
Accepted
time: 3461ms
memory: 472600kb

Test #37:

score: 30
Accepted
time: 2234ms
memory: 470444kb

Test #38:

score: 30
Accepted
time: 1577ms
memory: 464668kb

Test #39:

score: 30
Accepted
time: 1641ms
memory: 469316kb

Test #40:

score: 30
Accepted
time: 2169ms
memory: 472660kb