QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#162947#7103. Red Black Treenotpasscet_6#AC ✓516ms28460kbC++142.6kb2023-09-03 18:01:422023-09-03 18:01:43

Judging History

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

  • [2023-09-03 18:01:43]
  • 评测
  • 测评结果:AC
  • 用时:516ms
  • 内存:28460kb
  • [2023-09-03 18:01:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
struct Edge {
	int v, nxt, w;
}e[N * 2];
int head[N], cot;
void add(int u, int v, int w) {
	e[++cot] = { v, head[u], w };
	head[u] = cot;
}
int n, m, s, q;
int red[N], dist[N];
int dep[N], loc[N], tot, fa[N], son[N], sz[N], top[N], dfn[N], depth[N];
void dfs1(int u, int from) {
	dep[u] = dep[from] + 1; sz[u] = 1;
	fa[u] = from;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == from) continue;
		dfs1(v, u);
		sz[u] += sz[v];
		if (sz[v] > sz[son[u]]) {
			son[u] = v;
		}
	}
}
void dfs2(int u, int fat) {
	dfn[u] = ++tot; top[u] = fat;
	loc[tot] = u;
	if (!son[u]) return;
	dfs2(son[u], fat);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
int getlca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) swap(x, y);
		y = fa[top[y]];
	}
	return (dep[x] > dep[y]) ? y : x;
}
void clear() {
	cot = 0, tot = 0;
	for (int i = 0; i <= n; i++) head[i] = 0;
	for (int i = 0; i <= n; i++) dist[i] = 1e15;
	for (int i = 0; i <= n; i++) sz[i] = 0, depth[i] = 0,
		son[i] = 0, top[i] = 0, dep[i] = 0, dfn[i] = 0, top[i] = 0;
}
void dfs(int u, int fat) {
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, w = e[i].w;
		if (v == fat) continue;
		dist[v] = min(dist[v], dist[u] + w);
		depth[v] = depth[u] + w;
		dfs(v, u);
	}
}
bool cmp(int a, int b) {
	return dist[a] > dist[b];
}
void solve() {
	cin >> n >> m >> q;
	clear();
	s = 1;
	for (int i = 1; i <= m; i++) {
		int x; cin >> x;
		dist[x] = 0;
	}
	for (int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	dfs(s, 0);
	dfs1(s, 0);
	dfs2(s, 0);

	while (q--) {
		int num; cin >> num;
		vector<int> v(num);
		int ans = 0;
		for (int i = 0; i < num; i++) {
			cin >> v[i];
			ans = max(ans, dist[v[i]]);
		}
		sort(v.begin(), v.end(), cmp);
		// for(auto x : v){
			// cout << x << ' ' << dist[x] << '\n';
		// }
		if (num == 1) {
			ans = 0;
		}
		else {
			ans = dist[v[1]];
		}
		int lca = v[0];
		int maxdep = 0;
		for (int i = 0; i < num; i++) {
			lca = getlca(lca, v[i]);
			maxdep = max(maxdep, depth[v[i]]);
			// cout << ans << '\n';
			int t = 0;
			if(i + 1 != num) t = dist[v[i + 1]];
			ans = min(ans, max({0ll, t, maxdep - depth[lca]}));
		}
		cout << ans << '\n';
	}
}
signed main() {
	std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 20264kb

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: 516ms
memory: 28460kb

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