QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#448023#7103. Red Black Treeship2077AC ✓405ms24488kbC++171.6kb2024-06-19 09:11:022024-06-19 09:11:03

Judging History

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

  • [2024-06-19 09:11:03]
  • 评测
  • 测评结果:AC
  • 用时:405ms
  • 内存:24488kb
  • [2024-06-19 09:11:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int M=1e5+5;
int n,m,q,idx;vector<pair<int,int>>adj[M];
int k[M],l[M],col[M],dfn[M],st[20][M];
ll ans,val[M],dep[M],mxdep[M];
int read(){
	int x=0;char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
	return x;
}
int cmp(int x,int y){return dfn[x]<dfn[y]?x:y;}
void dfs(int x,int f,int lst){
	if (col[x]) lst=x;
	val[x]=dep[x]-dep[lst];
	st[0][dfn[x]=++idx]=f;
	for (auto [y,z]:adj[x]){
		if (y==f) continue;
		dep[y]=dep[x]+z;dfs(y,x,lst);
	}
}
int lca(int x,int y){
	if (x==y) return x;
	if ((x=dfn[x])>(y=dfn[y])) swap(x,y);
	int k=31^__builtin_clz(y-x++);
	return cmp(st[k][x],st[k][y+1-(1<<k)]);
}
void solve(){
	n=read();m=read();q=read();
	for (int i=1;i<=n;i++) col[i]=0,adj[i].clear();
	for (int i=1;i<=m;i++) col[read()]=1;
	for (int i=1;i<n;i++){
		int x=read(),y=read(),z=read();
		adj[x].emplace_back(y,z);
		adj[y].emplace_back(x,z);
	} idx=0;dfs(1,0,0);
	int lg=31^__builtin_clz(n);
	for (int j=1;j<=lg;j++)
		for (int i=1;i+(1<<j)-1<=n;i++)
			st[j][i]=cmp(st[j-1][i],st[j-1][i+(1<<j-1)]);
	while (q--){ m=read();ans=1ll<<60;
		for (int i=1;i<=m;i++) k[i]=read(); k[m+1]=0;
		sort(k+1,k+m+1,[&](int x,int y){return val[x]>val[y];});
		for (int i=1;i<=m;i++) l[i]=k[i],mxdep[i]=dep[k[i]];
		for (int i=2;i<=m;i++) l[i]=lca(l[i-1],l[i]),mxdep[i]=max(mxdep[i-1],mxdep[i]);
		for (int i=1;i<=m;i++) ans=min(ans,max(mxdep[i]-dep[l[i]],val[k[i+1]]));
		printf("%lld\n",ans);
	}
}
int main(){int T=read();while (T--) solve();return 0;}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 405ms
memory: 24488kb

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