QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165874#7103. Red Black Treeucup-team1074AC ✓881ms47116kbC++202.7kb2023-09-05 22:29:072023-09-05 22:29:08

Judging History

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

  • [2023-09-05 22:29:08]
  • 评测
  • 测评结果:AC
  • 用时:881ms
  • 内存:47116kb
  • [2023-09-05 22:29:07]
  • 提交

answer

//
// Created by lv_shen on 2023/9/2.
//

#include <bits/stdc++.h>

#define endl "\n"
//#define int long long
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
typedef pair<int, LL> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using i64 = long long;

LL n, m, q, fa[N][26], dep[N], depcost[N], cost[N];
int Log2[N];
vector<PII> g[N];
bool st[N];
int red[N];
void dfs (int x, int fath = 0, LL w = 0) {
	if (st[x])
		return;
	st[x] = true;
	dep[x] = dep[fath] + 1;
	fa[x][0] = fath;
	depcost[x] = depcost[fath] + w;
	cost[x] = min (cost[x], cost[fath] + w);
	//cost[x] = cost[fath] + w;
	//if (red[x]) cost[x] = 0;
	for (int i = 1; i <= 25; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
	}
	for (auto [y, ww] : g[x]) {
		dfs (y, x, ww);
	}
}

int lca (int x, int y) {
	if (dep[x] < dep[y])
		swap (x, y);
	while (dep[x] != dep[y])
		x = fa[x][Log2[dep[x] - dep[y]]];
	if (x == y) return x;
	for (int j = 25; j >= 0; j--) {
		if (fa[x][j] != fa[y][j]) {
			x = fa[x][j], y = fa[y][j];
		}
	}
	return fa[x][0];
}

bool cmp (int a, int b) {
	return cost[a] < cost[b];
}

void solve () {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) cost[i] = 1e18;
	// for (int i = 0; i <= n; i++) {
	// 	dep[i] = depcost[i] = 0;
	// 	cost[i] = 1e18;
	// 	red[i] = false;
	// 	g[i].clear ();
	// 	st[i] = false;
	// }
	for (int i = 0; i < m; i++) {
		int r;
		cin >> r;
		red[r] = true;
		cost[r] = 0;
	}

	for (int i = 1; i < n; i++) {
		int u, v;
		LL w;
		cin >> u >> v >> w;
		g[u].emplace_back (v, w);
		g[v].emplace_back (u, w);
	}

	fa[1][0] = 0;
	dfs (1);
	// for (int i = 1; i <= n; i++) {
	// 	cout << cost[i] << " " << depcost[i] << endl;
	// }
	while (q--) {
		int k;
		cin >> k;
		vector<int> v;
		for (int i = 0; i < k; i++) {
			int t;
			cin >> t;
			v.push_back (t);
		}
		sort (v.begin (), v.end (), cmp);
		i64 ans = cost[v[k - 1]];
		int l = v[k - 1];
		i64 maxdep = depcost[v[k - 1]];
		for (int i = k - 1; i >= 0; i--) {
			maxdep = std::max (maxdep, depcost[v[i]]);
			l = lca (l, v[i]);
			ans = std::min (ans, std::max ((i ? cost[v[i - 1]] : 0LL), maxdep - depcost[l]));
		}
		std::cout << ans << "\n";
	}
	for (int i = 0; i <= n; i++) {
		dep[i] = depcost[i] = 0;
		cost[i] = 1e18;
		red[i] = false;
		g[i].clear ();
		st[i] = false;
	}

}

signed main () {
	std::ios::sync_with_stdio (false);
	std::cin.tie (nullptr);
	std::cout.tie (nullptr);

	int t;
	cin >> t;
	for (int i = 2; i < N; ++i)
		Log2[i] = Log2[i / 2] + 1;
	// for (int i = 1; i <= 1000; i++) {
	// 	cout << i << " " << Log2[i] << endl;
	// }
	while (t--) {
		solve ();
	}

	return 0;
}


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

详细

Test #1:

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

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: 881ms
memory: 47116kb

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