QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#266595#7103. Red Black TreeUtopianZ#TL 2ms8368kbC++142.1kb2023-11-26 15:39:282023-11-26 15:39:28

Judging History

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

  • [2023-11-26 15:39:28]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:8368kb
  • [2023-11-26 15:39:28]
  • 提交

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],hs[maxn],ltop[maxn],fa[maxn],siz[maxn];
int lid[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;siz[u]=1;
	for(auto v:to[u])if(v.fi^f){
		dist[v.fi]=dist[u]+v.se;dfs(v.fi,u);
		siz[u]+=siz[v.fi];
		if(siz[hs[u]]<siz[v.fi])hs[u]=v.fi;
	}
	return ;
}
void build(int u,int f=0){
	if(u==hs[f])ltop[u]=ltop[f];
	else ltop[u]=u;
	for(auto v:to[u])if(v.fi^f)build(v.fi,u);
	return ;
}
int lca(int u,int v){
	while(ltop[u]^ltop[v]){
		if(dep[ltop[u]]>dep[ltop[v]])swap(u,v);
		v=fa[ltop[v]];
	}
	if(dep[u]>dep[v])swap(u,v);
	return u;
}
bool check(long long mid){
	int nlca=0;
	for(int i=1;i<=dsiz;i++)if(dist[toquer[i]]-dist[lid[toquer[i]]]>mid){
		if(!nlca)nlca=toquer[i];
		else nlca=lca(nlca,toquer[i]);
	}
	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();
	for(int i=1;i<=n;i++){
		to[i].clear();isr[i]=false;ltop[i]=hs[i]=dep[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(1);
	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){
			int 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;
}

详细

Test #1:

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

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: -100
Time Limit Exceeded

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:


result: