QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#163214#7103. Red Black Treeucup-team1001AC ✓813ms26024kbC++2.6kb2023-09-03 22:10:432023-09-03 22:10:44

Judging History

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

  • [2023-09-03 22:10:44]
  • 评测
  • 测评结果:AC
  • 用时:813ms
  • 内存:26024kb
  • [2023-09-03 22:10:43]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define LL __int128
#define rep(i,l,r) for(ll i = l; l <= r ? i <= r : i >= r;l <= r ? ++i : --i)
#define irep(i,l,r) for(ll i = l; i <= r; ++i)
#define drep(i,r,l) for(ll i = r; i >= l; --i)
#define abs(x) (x > 0 ? x : -x)
#define ceil(pp,qq) ((pp>0)^(qq>0)?-abs(pp)/abs(qq):pp%qq?pp/qq+1:pp/qq)
#define floor(pp,qq) ((pp>0)^(qq>0)?-ceil(abs(pp),abs(qq)):pp/qq)
using namespace std;
inline ll read(){
	ll s=0; bool fl = 0;
	char chcc=getchar();
	while(chcc<'0'||chcc>'9'){if(chcc == '-')fl = 1;chcc = getchar();}
	while(chcc>='0'&&chcc<='9') s=(s<<3)+(s<<1)+(chcc^48),chcc=getchar();
	return fl?-s:s;
}
const int N = 100999;
const long long llinf = 100000000000000000;
int ist[N], fa[N][24], S, dpt[N];
ll d[N];
vector<array<int,2>>g[N];
vector<array<int,3>>edge;

void dfs(int x, int dp){
	dpt[x] = dp, S = max(S, dpt[x]);
	for(auto [v,w] : g[x]){
		if(d[v] || v == 1)continue;
		fa[v][0] = x, d[v] = d[x] + w;
		dfs(v, dp + 1);
	}
}

int lca(int u,int v){
	if(u == v)return u;
	if(dpt[u] < dpt[v])swap(u,v);
	for(int i = S; i >= 0; -- i)
		if(dpt[fa[u][i]] >= dpt[v])u = fa[u][i];
	if(u == v)return u;
	for(int i = S; i >= 0; --i){
		if(fa[u][i] != fa[v][i])u = fa[u][i], v = fa[v][i];
	}
	return fa[u][0];
}

void solve(){
	int n = read(), m = read(), q = read();
	edge.clear();
	irep(i,1,n)g[i].clear();
	irep(i,1,n)ist[i] = 0, g[i].clear(), d[i] = 0, dpt[i] = 0;
	while(m --)ist[read()] = 1;
	
	irep(i,0,n-2){
		int u = read(), v = read(), w = read();
		edge.push_back({u,v,w});
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	dfs(1,0);
	irep(i,1,n)g[i].clear();
	for(auto [u,v,w] : edge){
		if(d[u] > d[v])swap(u,v);
		if(ist[v])continue;
		if(ist[u])u = 1;
		g[u].push_back({v,w});
		g[v].push_back({u,w});	
	}
	irep(i,1,n)d[i] = 0, dpt[i] = 0;
	fa[1][0] = 1, S = 0;
	dfs(1,0);
	S = log2(S) + 1;
	for(int s = 1; s <= S; ++ s)
		for(int i = 1; i <= n; ++i)
			fa[i][s] = fa[fa[i][s - 1]][s - 1];
	while(q --){
		int sk = read(), c = 0;
		ll ans = llinf;
		vector<int>node;
		for(int i = 1; i <= sk; ++i){
			int x = read();
			if(!ist[x])node.push_back(x);
		}
		if(node.size() == 0){puts("0");continue;}
		sort(node.begin(), node.end(), [](int u,int v){return d[u] > d[v];});
		for(int i = 0, x = node[0]; i < node.size(); i ++, x = node[i]){
			if(c == 0)c = x;
			else c = lca(c, x);
			if(i != node.size() - 1)ans = min(ans, max(d[node[0]] - d[c], d[node[i + 1]]));
			else ans = min(ans, d[node[0]] - d[c]);
		}
		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: 1ms
memory: 7196kb

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: 813ms
memory: 26024kb

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