QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#695519#7103. Red Black TreeMine_King#AC ✓486ms14684kbC++142.7kb2024-10-31 20:12:242024-10-31 20:12:25

Judging History

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

  • [2024-10-31 20:12:25]
  • 评测
  • 测评结果:AC
  • 用时:486ms
  • 内存:14684kb
  • [2024-10-31 20:12:24]
  • 提交

answer

// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int T, n, m, q, clr[100005], anc[100005];
long long dist[100005];
struct graph {
	int tot, hd[100005];
	int nxt[200005], to[200005], dt[200005];

	void clear(int n) {tot = 0; memset(hd, 0, sizeof(int) * n); return;}
	void add(int u, int v, int w) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		dt[tot] = w;
		return;
	}
} g;
int fa[100005], siz[100005], son[100005], depth[100005], top[100005];

void dfs1(int now, int F) {
	fa[now] = F, depth[now] = depth[F] + 1, siz[now] = 1, son[now] = 0;
	if (clr[now]) anc[now] = now;
	else anc[now] = anc[F];
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != F) {
			dist[g.to[i]] = dist[now] + g.dt[i];
			dfs1(g.to[i], now);
			siz[now] += siz[g.to[i]];
			if (siz[g.to[i]] > siz[son[now]]) son[now] = g.to[i];
		}
	return;
}
void dfs2(int now, int F) {
	top[now] = F;
	if (!son[now]) return;
	dfs2(son[now], F);
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != fa[now] && g.to[i] != son[now]) dfs2(g.to[i], g.to[i]);
	return;
}
int getLCA(int u, int v) {
	while (top[u] != top[v])
		if (depth[top[u]] > depth[top[v]]) u = fa[top[u]];
		else v = fa[top[v]];
	return depth[u] < depth[v] ? u : v;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &q);
		for (int i = 1; i <= n; i++) clr[i] = 0;
		while (m--) {
			int x;
			scanf("%d", &x);
			clr[x] = 1;
		}
		g.clear(n + 5);
		for (int i = 1; i < n; i++) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			g.add(u, v, w), g.add(v, u, w);
		}
		dfs1(1, 0), dfs2(1, 1);
		while (q--) {
			int len;
			scanf("%d", &len);
			vector<int> vec(len);
			for (int i = 0; i < len; i++) scanf("%d", &vec[i]);
			sort(vec.begin(), vec.end(), [](const int &x, const int &y) {
				return dist[x] - dist[anc[x]] > dist[y] - dist[anc[y]];
			});
			vec.push_back(1);
			long long ans = dist[vec[0]] - dist[anc[vec[0]]];
			int vert = vec[0];
			for (int i = 0; i < len; i++) {
				if (anc[vec[i]] != anc[vec[0]]) break;
				vert = getLCA(vert, vec[i]);
				ans = min(ans, max(dist[vec[0]] - dist[vert], dist[vec[i + 1]] - dist[anc[vec[i + 1]]]));
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}
/*
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 4 5 7 8
5
4 7 8 10 11
3
3 4 5 12
8
3 2 3
1 2
1 2 1
1 3 1
1 1
0
2 1 2
0
3 1 2 3
0

*/

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8168kb

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: 486ms
memory: 14684kb

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