QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156453#7103. Red Black Treeucup-team1004#AC ✓1597ms21848kbC++141.8kb2023-09-02 13:35:062023-09-02 14:51:11

Judging History

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

  • [2023-09-02 14:51:11]
  • 评测
  • 测评结果:AC
  • 用时:1597ms
  • 内存:21848kb
  • [2023-09-02 13:35:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
const ll INF=1e18;
int T,n,m,q,col[N],f[N];
ll dis[N];
vector<pair<int,int> >to[N];
namespace Path{
	int dep[N],fa[N],top[N],son[N],siz[N];
	#define v e.first
	#define w e.second
	void dfs1(int u){
		if(col[u])f[u]=u;
		else f[u]=f[fa[u]];
		dep[u]=dep[fa[u]]+1,siz[u]=1;
		son[u]=0;
		for(auto e:to[u])if(v^fa[u]){
			dis[v]=dis[u]+w;
			fa[v]=u,dfs1(v);
			siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void dfs2(int u,int t){
		top[u]=t;
		if(son[u])dfs2(son[u],t);
		for(auto e:to[u])if(v^fa[u]&&v^son[u])dfs2(v,v);
	}
	#undef v
	#undef w
	void init(){
		dfs1(1),dfs2(1,1);
	}
	int LCA(int u,int v){
//		cerr<<u<<' '<<v<<endl;
		for(;top[u]^top[v];u=fa[top[u]]){
			if(dep[top[u]]<dep[top[v]])swap(u,v);
		}
		return dep[u]<dep[v]?u:v;
	}
}
using Path::LCA;
void get(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x),col[x]=1;
	}
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		to[u].push_back({v,w}),to[v].push_back({u,w});
	}
	Path::init();
	for(int t;q--;){
		scanf("%d",&t);
		vector<int>a(t);
		for(int i=0;i<t;i++)scanf("%d",&a[i]);
		auto chk=[&](ll mid){
			vector<int>p;
			for(int i=0;i<t;i++){
				if(dis[a[i]]-dis[f[a[i]]]>mid){
					p.push_back(a[i]);
				}
			}
			if(p.empty())return 1;
			int x=p[0];
			for(int i=1;i<p.size();i++)x=LCA(x,p[i]);
			for(int i:p)if(dis[i]-dis[x]>mid)return 0;
			return 1;
		};
		ll l=-1,r=INF,mid;
		for(;l+1<r;){
			mid=(l+r)>>1;
			if(chk(mid))r=mid;
			else l=mid;
		}
		printf("%lld\n",r);
	}
}
void clr(){
	for(int i=1;i<=n;i++){
		col[i]=0;
		to[i].clear();
	}
}
int main(){
	for(scanf("%d",&T);T--;clr())get();
	return 0;
}

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

詳細信息

Test #1:

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

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: 1597ms
memory: 21848kb

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