QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#850883#4408. 燃烧的呐球275307894a#100 ✓7319ms816468kbC++146.3kb2025-01-10 12:34:482025-01-10 12:34:49

Judging History

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

  • [2025-01-10 12:34:49]
  • 评测
  • 测评结果:100
  • 用时:7319ms
  • 内存:816468kb
  • [2025-01-10 12:34:48]
  • 提交

answer

#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=N*20+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(28382);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#ifdef LOCAL
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
	#else 
	#define gdb(...) void()
	#endif
}using namespace Debug;
int n,m,k;vector<int> S[N];
int bg[N],en[N],bh,siz[N];
void make(int x,int La){
	bg[x]=++bh;siz[x]=1;
	for(int i:S[x]) make(i,x),siz[x]+=siz[i];
	en[x]=bh;
}
int cnt,fa[N],c[N],X[N],Y[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
const pii If=make_pair(INF,-1);
struct node{
	pii a,b;
	node operator +(const node &B)const{
		pii mi=min(a,B.a),ms=If;
		if(a.se^mi.se) ms=min(ms,a);else ms=min(ms,b);
		if(B.a.se^mi.se) ms=min(ms,B.a);else ms=min(ms,B.b);
		return (node){mi,ms};
	}
	node operator +(const int &B)const{
		return (node){make_pair(a.fi+B,a.se),make_pair(b.fi+B,b.se)};
	}
}w[N];
const node inf=(node){make_pair(INF,0),If};
vector<int> Q1[N],Q2[N];
node w1[N],w2[N],w3[N],w4[N];
void dfs(int x,int La){
	w1[x]=w1[La];w2[x]=w2[La];
	w3[x]=w4[x]=inf;
	for(int i:Q1[x]){
		w1[x]=w1[x]+(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),If};
		w3[x]=w3[x]+(node){make_pair(-siz[X[i]]+siz[Y[i]],c[i]),If};
	}
	for(int i:Q2[x]){
		w2[x]=w2[x]+(node){make_pair(siz[Y[i]]+siz[X[i]],c[i]),If};
		w4[x]=w4[x]+(node){make_pair(-siz[Y[i]]+siz[X[i]],c[i]),If};
	}
	for(int i:S[x]) dfs(i,x),w3[x]=w3[x]+w3[i],w4[x]=w4[x]+w4[i];
	for(int i:Q1[x]){
		w[i]=w[i]+(w1[x]+-siz[X[i]]+siz[Y[i]]);
		w[i]=w[i]+(w3[x]+siz[X[i]]+siz[Y[i]]);
	}
	for(int i:Q2[x]){
		w[i]=w[i]+(w2[x]+-siz[Y[i]]+siz[X[i]]);
		w[i]=w[i]+(w4[x]+siz[Y[i]]+siz[X[i]]);
	}
}
int st[N],sh;
int r1[N],r2[N];
namespace PreT{
	node f[M],g[M];int cnt,L[M],R[M];
	void clr(){
		for(int i=0;i<=cnt;i++) L[i]=R[i]=0,f[i]=g[i]=inf;
		f[0]=g[0]=inf;cnt=0;
	}
	void cp(int &v){
		f[++cnt]=f[v];L[cnt]=L[v];R[cnt]=R[v];g[cnt]=g[v];
		v=cnt;
	}
	void add(int x,int y,node w,int &v,int l=1,int r=n){
		cp(v);f[v]=f[v]+w;if(x<=l&&r<=y){g[v]=g[v]+w;return;}
		int m=l+r>>1;x<=m&&(add(x,y,w,L[v],l,m),0);y>m&&(add(x,y,w,R[v],m+1,r),0);
	}
	node qry(int x,int y,int v,int l=1,int r=n){
		if(x<=l&&r<=y) return f[v];int m=l+r>>1;
		return (x<=m?qry(x,y,L[v],l,m):inf)+(y>m?qry(x,y,R[v],m+1,r):inf)+g[v];
	}
}
int r3[N],r4[N];
namespace Tree{
	node f[M],g[M];int cnt,L[M],R[M];
	void clr(){
		for(int i=0;i<=cnt;i++) L[i]=R[i]=0,f[i]=g[i]=inf;
		f[0]=g[0]=inf;cnt=0;
	}
	void add(int x,int y,node w,int &v,int l=1,int r=n){
		if(!v){
			v=++cnt;f[v]=g[v]=inf;
		}
		f[v]=f[v]+w;
		if(x<=l&&r<=y){
			g[v]=g[v]+w;
			return;
		}
		int m=l+r>>1;x<=m&&(add(x,y,w,L[v],l,m),0);y>m&&(add(x,y,w,R[v],m+1,r),0);
	}
	node qry(int x,int y,int v,int l=1,int r=n){
		if(x<=l&&r<=y) return f[v];int m=l+r>>1;
		return (x<=m?qry(x,y,L[v],l,m):inf)+(y>m?qry(x,y,R[v],m+1,r):inf)+g[v];
	}
	int merge(int x,int y,int l=1,int r=n){
		if(!x||!y) return x+y;
		f[x]=f[x]+f[y];g[x]=g[x]+g[y];
		if(l==r) return x;
		int m=l+r>>1;L[x]=merge(L[x],L[y],l,m);R[x]=merge(R[x],R[y],m+1,r);
		return x;
	}
}
void DP(int x,int La){
	r1[x]=r1[La];r2[x]=r2[La];
	r3[x]=r4[x]=0;
	for(int i:Q1[x]){
		PreT::add(bg[Y[i]],bg[Y[i]],(node){make_pair(siz[X[i]]-siz[Y[i]],c[i]),If},r1[x]);
		PreT::add(bg[Y[i]],en[Y[i]],(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),If},r2[x]);
		Tree::add(bg[Y[i]],bg[Y[i]],(node){make_pair(-siz[X[i]]-siz[Y[i]],c[i]),If},r3[x]);
		// gdb(i,bg[Y[i]],-siz[X[i]]-siz[Y[i]]);
		Tree::add(bg[Y[i]],en[Y[i]],(node){make_pair(-siz[X[i]]+siz[Y[i]],c[i]),If},r4[x]);
	}
	for(int i:Q1[x]){
		/*for(int y=1;y<=sh;y++){
			int j=st[y];
			int res=(siz[X[j]]-siz[X[i]]);
			if(bg[Y[j]]<=bg[Y[i]]&&bg[Y[i]]<=en[Y[j]]){
				res+=siz[Y[j]]-siz[Y[i]];
				// w[i]=w[i]+(node){make_pair(res,c[j]),If};
				// w[j]=w[j]+(node){make_pair(res,c[i]),If};
			}
			else if(bg[Y[i]]<=bg[Y[j]]&&bg[Y[j]]<=en[Y[i]]){
				res+=siz[Y[i]]-siz[Y[j]];
				// w[i]=w[i]+(node){make_pair(res,c[j]),If};
				// w[j]=w[j]+(node){make_pair(res,c[i]),If};
			}
		}*/
		st[++sh]=i;
		w[i]=w[i]+(PreT::qry(bg[Y[i]],en[Y[i]],r1[x])+-siz[X[i]]+siz[Y[i]]);
		w[i]=w[i]+(PreT::qry(bg[Y[i]],bg[Y[i]],r2[x])+-siz[X[i]]+-siz[Y[i]]);
	}
	for(int i:S[x]) DP(i,x),r3[x]=Tree::merge(r3[x],r3[i]),r4[x]=Tree::merge(r4[x],r4[i]);
	for(int i:Q1[x]){
		w[i]=w[i]+(Tree::qry(bg[Y[i]],en[Y[i]],r3[x])+siz[X[i]]+siz[Y[i]]);
		// gdb(bg[Y[i]],en[Y[i]],siz[X[i]]+siz[Y[i]],i);
		w[i]=w[i]+(Tree::qry(bg[Y[i]],bg[Y[i]],r4[x])+siz[X[i]]+-siz[Y[i]]);
	}
	for(int i:Q1[x]) sh--;
}
void Solve(){
	scanf("%d%d",&n,&m);
	// if(m>1000) return;
	for(int i=2;i<=n;i++){
		int x;scanf("%d",&x);
		S[x].push_back(i);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&X[i],&Y[i]);
		Q1[X[i]].push_back(i),Q2[Y[i]].push_back(i);
	} 
	make(1,0);
	iota(fa+1,fa+m+1,1);
	cnt=m;
	ll ans=0;
	while(cnt^1){
		for(int i=1;i<=m;i++) c[i]=GF(i);
		node res=inf;
		for(int i=1;i<=m;i++) res=res+(node){make_pair(siz[X[i]]+siz[Y[i]],c[i]),make_pair(INF,0)};
		for(int i=1;i<=m;i++) w[i]=res+siz[X[i]]+siz[Y[i]];
		w1[0]=w2[0]=inf;dfs(1,0);
		PreT::clr();Tree::clr();
		DP(1,0);
		gdb(w[2].a.fi,w[2].b.fi);
		for(int i=1;i<=m;i++) w[GF(i)]=w[GF(i)]+w[i];
		vector<tuple<int,int,int> > e;
		for(int i=1;i<=m;i++) if(fa[i]==i){
			// gdb(i,w[i].a.fi,w[i].a.se,w[i].b.fi,w[i].b.se);
			for(pii s:{w[i].a,w[i].b}) if(s.se>0&&GF(s.se)^GF(i)){e.emplace_back(s.fi,s.se,i);break;}
		}
		sort(all(e));
		for(auto [w,a,b]:e){
			if(GF(a)^GF(b)) ans+=w,fa[GF(a)]=GF(b),cnt--;
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int t=1;
	// scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 12ms
memory: 112448kb

Test #2:

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

Test #3:

score: 10
Accepted
time: 27ms
memory: 115632kb

Test #4:

score: 10
Accepted
time: 15ms
memory: 115708kb

Test #5:

score: 10
Accepted
time: 25ms
memory: 116036kb

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 10
Accepted
time: 2030ms
memory: 281744kb

Test #7:

score: 10
Accepted
time: 1208ms
memory: 279124kb

Test #8:

score: 10
Accepted
time: 804ms
memory: 271116kb

Test #9:

score: 10
Accepted
time: 777ms
memory: 274964kb

Test #10:

score: 10
Accepted
time: 1130ms
memory: 278836kb

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 10
Accepted
time: 3372ms
memory: 386940kb

Test #12:

score: 10
Accepted
time: 2112ms
memory: 383664kb

Test #13:

score: 10
Accepted
time: 1581ms
memory: 367612kb

Test #14:

score: 10
Accepted
time: 1545ms
memory: 376176kb

Test #15:

score: 10
Accepted
time: 2072ms
memory: 377452kb

Subtask #4:

score: 20
Accepted

Test #16:

score: 20
Accepted
time: 724ms
memory: 209116kb

Test #17:

score: 20
Accepted
time: 850ms
memory: 213320kb

Test #18:

score: 20
Accepted
time: 555ms
memory: 213208kb

Test #19:

score: 20
Accepted
time: 567ms
memory: 211232kb

Test #20:

score: 20
Accepted
time: 714ms
memory: 213148kb

Subtask #5:

score: 10
Accepted

Test #21:

score: 10
Accepted
time: 7283ms
memory: 812036kb

Test #22:

score: 10
Accepted
time: 7280ms
memory: 812484kb

Test #23:

score: 10
Accepted
time: 7319ms
memory: 811960kb

Test #24:

score: 10
Accepted
time: 7229ms
memory: 812004kb

Test #25:

score: 10
Accepted
time: 7189ms
memory: 816468kb

Subtask #6:

score: 10
Accepted

Test #26:

score: 10
Accepted
time: 1501ms
memory: 520716kb

Test #27:

score: 10
Accepted
time: 1511ms
memory: 522932kb

Test #28:

score: 10
Accepted
time: 1512ms
memory: 518012kb

Test #29:

score: 10
Accepted
time: 1539ms
memory: 523588kb

Test #30:

score: 10
Accepted
time: 1577ms
memory: 523452kb

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: 5112ms
memory: 563992kb

Test #32:

score: 30
Accepted
time: 2986ms
memory: 555660kb

Test #33:

score: 30
Accepted
time: 2316ms
memory: 542260kb

Test #34:

score: 30
Accepted
time: 2317ms
memory: 550484kb

Test #35:

score: 30
Accepted
time: 2881ms
memory: 546936kb

Test #36:

score: 30
Accepted
time: 5180ms
memory: 568632kb

Test #37:

score: 30
Accepted
time: 3011ms
memory: 550492kb

Test #38:

score: 30
Accepted
time: 2341ms
memory: 538140kb

Test #39:

score: 30
Accepted
time: 2350ms
memory: 541340kb

Test #40:

score: 30
Accepted
time: 2915ms
memory: 547976kb