QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461851#7103. Red Black Tree1L1YAAC ✓717ms28520kbC++232.3kb2024-07-03 05:16:542024-07-03 05:16:55

Judging History

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

  • [2024-07-03 05:16:55]
  • 评测
  • 测评结果:AC
  • 用时:717ms
  • 内存:28520kb
  • [2024-07-03 05:16:54]
  • 提交

answer

//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=2e5+11;
const int lg=23;

int n,m,q,t,a[N],h[N],par[lg][N];
vector<pii> adj[N];
ll d[N],val[N];

void dfs(int v,int p=0){
	for(auto [u,w]: adj[v])
		if(u!=p){
			h[u]=h[v]+1;
			val[u]=val[v]+w;
			if(a[u])	val[u]=0;
			d[u]=d[v]+w;
			par[0][u]=v;
			dfs(u,v);
		}
}

int jump(int v,int k){
	for(int i=0;i<lg;i++)
		if(k>>i & 1)
			v=par[i][v];
	return v;
}

int lca(int u,int v){
	if(h[u]>h[v])	swap(u,v);
	v=jump(v,h[v]-h[u]);
	if(v==u)	return v;
	for(int i=lg-1;~i;i--)
		if(par[i][u]!=par[i][v])
			u=par[i][u],v=par[i][v];
	return par[0][v];
}

void slv(){
	cin >> n >> m >> q;
	for(int i=1;i<=m;i++){
		int v;cin >> v;
		a[v]=1;
	}
	for(int i=1;i<n;i++){
		int u,v,w;
		cin >> u >> v >> w;
		adj[u].Pb({v,w});
		adj[v].Pb({u,w});
	}
	dfs(1);
	for(int i=1;i<lg;i++)
		for(int v=1;v<=n;v++)
			par[i][v]=par[i-1][par[i-1][v]];
	while(q--){
		int k;cin >> k;
		vector<pll> vc;
		for(int i=1;i<=k;i++){
			int v;cin >> v;
			vc.Pb({val[v],v});
		}
		sort(all(vc),greater<>());
		vc.Pb({0,1});
		int w=0;
		ll mx=0,ans=vc[0].F;
		for(int i=0;i<k;i++){
			if(!w)	w=vc[i].S;
			else	w=lca(w,vc[i].S);
			mx=max(mx,d[vc[i].S]);
			ans=min(ans,max(vc[i+1].F,mx-d[w]));
		}
		cout << ans << endl;
	}
}

void clr(){
	fill(a,a+n+1,0);
	for(int i=1;i<=n;i++)	adj[i].clear();
}

int main(){
	FastIO

	cin >> t;
	while(t--){
		slv();
		clr();
	}

	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 717ms
memory: 28520kb

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