QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225899#7103. Red Black Treefzj2007#AC ✓593ms45676kbC++143.9kb2023-10-25 11:21:032023-10-25 11:21:03

Judging History

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

  • [2023-10-25 11:21:03]
  • 评测
  • 测评结果:AC
  • 用时:593ms
  • 内存:45676kb
  • [2023-10-25 11:21:03]
  • 提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
template<typename T>inline void read(T &x){
	x=0;
	char ch=getchar();
	bool flag=0;
	while(ch>'9'||ch<'0') flag=flag||ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=flag?-x:x;
}
template<typename T,typename ...Args>inline void read(T &x,Args &...args){
	read(x),read(args...);
}
template<typename T>inline void prt(T x){
	if(x>9) prt(x/10);
	putchar(x%10+'0');
}
template<typename T>inline void put(T x){
	if(x<0) putchar('-'),x=-x;
	prt(x);
}
template<typename T>inline void put(char ch,T x){
	put(x),putchar(ch);
}
template<typename T,typename ...Args>inline void put(char ch,T x,Args ...args){
	put(ch,x),put(ch,args...);
}
#define N 200005
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
ll pre[N];
int n,m,q,col[N];
int dfn[N],idx,st[N][20],lg[N],dep[N],fir[N],fath[N];
vector<pair<int,int>> e[N];
vector<int> g[N];
inline int Min(int x,int y){
	return dep[x]<dep[y]?x:y;
}
inline void dfs(int x,int fa){
	dfn[x]=++idx,st[idx][0]=x,dep[x]=dep[fa]+1;
	fir[x]=col[x]?x:fir[fa],fath[x]=fa;
	for(auto v:e[x])
		if(v.first!=fa) pre[v.first]=pre[x]+v.second,dfs(v.first,x);
}
inline int lca(int x,int y){
	if(x==y) return x;
	x=dfn[x],y=dfn[y];
	if(x>y) swap(x,y);
	x++;
	int k=lg[y-x+1];
	return fath[Min(st[x][k],st[y-(1<<k)+1][k])];
}
int k,pos[N],vis[N];
int sta[N],tp;
vector<int> used;
inline void build(){
	tp=0,sta[++tp]=1,used.emplace_back(1);
	for(int i=1;i<=k;i++){
		if(sta[tp]==pos[i]) continue;
		int f=lca(sta[tp],pos[i]);
		while(tp>1&&dep[sta[tp-1]]>=dep[f]) g[sta[tp-1]].emplace_back(sta[tp]),tp--;
		if(sta[tp]!=f) g[f].emplace_back(sta[tp]),sta[tp]=f,used.emplace_back(f);
		sta[++tp]=pos[i],used.emplace_back(pos[i]);
	}
	while(tp>1) g[sta[tp-1]].emplace_back(sta[tp]),tp--;
}
ll A[N],B[N],ans;
inline void dp(int x){
	for(auto v:g[x]) dp(v);
	if(vis[x]&&!col[x]) B[x]=A[x]=0;
	else B[x]=-inf,A[x]=0; 
	for(auto v:g[x]){
		A[x]=max(A[x],A[v]);
		if(dep[fir[v]]<dep[x]) B[x]=max(B[x],B[v]+pre[v]-pre[x]);
		else A[x]=max(A[x],B[v]+pre[v]-pre[fir[v]]);		
	}
}
inline void solve(int x,ll lftans){
	ans=min(ans,max(lftans,max(A[x],B[x])));
	int num=0,pos=0;
	for(auto v:g[x]) 
		if(B[v]>=0&&!fir[v]) num++,pos=v;
	if(vis[x]&&!fir[x]) return;
	if(!g[x].size()||num>=2) return;
	if(num){
		ll maxa=0;
		for(auto v:g[x])
			if(v!=pos) maxa=max(maxa,max(A[v],B[v]+pre[v]-pre[fir[v]]));
		if(vis[x]) maxa=max(maxa,pre[x]-pre[fir[x]]);
		solve(pos,max(lftans,maxa));
		return;
	}
	vector<ll> L(g[x].size()),R(g[x].size());
	for(int i=0;i<g[x].size();i++){
		int v=g[x][i];
		L[i]=max(A[v],B[v]+pre[v]-pre[fir[v]]);
		if(i) L[i]=max(L[i],L[i-1]);
	}
	for(int i=(int)g[x].size()-1;i>=0;i--){
		int v=g[x][i];
		R[i]=max(A[v],B[v]+pre[v]-pre[fir[v]]);
		if(i<(int)g[x].size()-1) R[i]=max(R[i],R[i+1]);
	}
	for(int i=0;i<g[x].size();i++){
		ll maxa=0,v=g[x][i];
		if(i) maxa=max(maxa,L[i-1]);
		if(i<(int)g[x].size()-1) maxa=max(maxa,R[i+1]);
		if(vis[x]) maxa=max(maxa,pre[x]-pre[fir[x]]);
		solve(v,max(lftans,maxa));
	}
}
inline void solve(){
	read(n,m,q);
	for(int i=1,x;i<=m;i++) read(x),col[x]=1;
	for(int i=1,u,v,w;i<n;i++)
		read(u,v,w),e[u].emplace_back(v,w),e[v].emplace_back(u,w);
	dfs(1,0);
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=Min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	while(q--){
		read(k);
		for(int i=1;i<=k;i++) read(pos[i]),vis[pos[i]]=1; 
		sort(pos+1,pos+k+1,[](const int &x,const int &y){return dfn[x]<dfn[y];});
		build();
		ans=inf,dp(1),solve(1,0);
		put('\n',ans);
		for(int i=1;i<=k;i++) vis[pos[i]]=0;
		for(auto v:used) g[v].clear();
		used.clear();
	}
}
inline void clear(){
	for(int i=1;i<=n;i++) col[i]=0,e[i].clear();
	idx=0;
}
int T;
int main(){
	for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
	read(T);
	while(T--) solve(),clear();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 22688kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 593ms
memory: 45676kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed