QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#266665#7103. Red Black TreeUtopianZ#AC ✓762ms35508kbC++142.3kb2023-11-26 16:26:592023-11-26 16:27:00

Judging History

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

  • [2023-11-26 16:27:00]
  • 评测
  • 测评结果:AC
  • 用时:762ms
  • 内存:35508kb
  • [2023-11-26 16:26:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int sum=0,fh=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')fh=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum*=10;
		sum+=c-'0';
		c=getchar();
	}
	return sum*fh;
}
#define maxn 100009
#define pb push_back
#define mp make_pair
#define fi first
#define se second
int n,m,q,t,dep[maxn],fa[maxn];
int lid[maxn],dfn[maxn<<1],tot=0,lg2[maxn<<1],stt[maxn];
long long dist[maxn];
vector<pair<int ,int > > to[maxn];
int toquer[maxn],dsiz;
bool isr[maxn]; 
void dfs(int u,int f=0){
	if(isr[u])lid[u]=u;
	else lid[u]=lid[f];
	fa[u]=f;
	dep[u]=dep[f]+1;
	stt[u]=++tot;dfn[tot]=u;
	for(auto v:to[u])if(v.fi^f){
		dist[v.fi]=dist[u]+v.se;dfs(v.fi,u);
		dfn[++tot]=u;
	}
	return ;
}
int st[maxn<<1][20];
void build(){
	lg2[0]=-1;
	for(int i=1;i<=tot;i++)st[i][0]=dfn[i],lg2[i]=lg2[i>>1]+1;
	for(int i=1;i<20;i++)for(int j=1;j+(1<<i)-1<=tot;j++){
		if(dep[st[j][i-1]]<dep[st[j+(1<<(i-1))][i-1]])st[j][i]=st[j][i-1];
		else st[j][i]=st[j+(1<<(i-1))][i-1];
	}
	return ;
}
int lca(int u,int v){
	int l=stt[u],r=stt[v];
	if(l>r)swap(l,r);
	int lg=lg2[r-l+1];
	if(dep[st[l][lg]]<dep[st[r-(1<<lg)+1][lg]])return st[l][lg];
	return st[r-(1<<lg)+1][lg];
}
bool check(long long mid){
	int nlca=0;
//	cout<<"mid:"<<mid<<endl;
	for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-dist[lid[toquer[i]]]>mid){
//		cout<<toquer[i]<<endl;
		if(!nlca)nlca=toquer[i];
		else nlca=lca(nlca,toquer[i]);
	}
//	cout<<nlca<<endl;
	for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-max(dist[lid[toquer[i]]],dist[nlca])>mid)return false;
	return true;
}
void solve(){
	n=read();m=read();q=read();
	tot=0;
	for(int i=1;i<=n;i++){
		to[i].clear();isr[i]=false;dep[i]=dist[i]=dfn[i]=0;
	}
	for(int i=1;i<=m;i++)isr[read()]=true;
	for(int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		to[u].pb(mp(v,w));to[v].pb(mp(u,w));
	}
	dfs(1);build();
	for(int i=1;i<=q;i++){
		dsiz=read();
		for(int j=1;j<=dsiz;j++)toquer[j]=read();
		long long l=0,r=1e14,ans=1e14;
		while(l<=r){
			long long mid=(l+r)>>1;
			if(check(mid))ans=mid,r=mid-1;
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
	return ;
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
	t=read();
	while(t--){
		solve();
	}
//	  fclose(stdin);
//    fclose(stdout);
	return 0;
}

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

详细

Test #1:

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

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: 762ms
memory: 35508kb

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