QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226852#7103. Red Black Treesine_and_cosine#AC ✓1565ms45220kbC++173.2kb2023-10-26 17:16:332023-10-26 17:16:33

Judging History

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

  • [2023-10-26 17:16:33]
  • 评测
  • 测评结果:AC
  • 用时:1565ms
  • 内存:45220kb
  • [2023-10-26 17:16:33]
  • 提交

answer

#include <bits/stdc++.h>

#pragma GCC optimize(2)
using namespace std;
#define int long long
#define endl '\n'
#define eb emplace_back
#define INF (int)(2e15)
#define pii pair<int, int>
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err(){cout<<'\n';cout.flush();}
template<class T, class... Ts>
void err(T arg, Ts... args) {
	cout<<arg<< ' ';
	err(args...);
}
void run() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> red(n + 1);
	for (int i = 1; i <= m; i++) {
		int now;
		cin >> now;
		red[now] = 1;
	}
	vector<vector<pii> > g(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].eb(v, w);
		g[v].eb(u, w);
	}
	
	constexpr int Log = 20;
	vector<int> depth(n + 1), dis(n + 1);
	vector<array<int, Log + 5> > anc(n + 1);
	vector<int> rdAnc(n + 1);
	function<void(int, int, int)> init = [&](int now, int father, int lstRd) -> void {
		anc[now][0] = father;
		depth[now] = depth[father] + 1;
		int nxRd = red[now] ? now : lstRd;
		rdAnc[now] = nxRd;
		for (auto p : g[now]) if (p.first != father) {
			dis[p.first] = dis[now] + p.second;
			init(p.first, now, nxRd);
		}
	};
	init(1, 1, 1);
	for (int j = 1; j <= Log; j++) {
		for (int i = 1; i <= n; i++) {
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
		}
	}
	auto rush = [&](int u, int h) -> int {
		for (int i = 0; i <= Log; i++) {
			if (h >> i & 1) u = anc[u][i];
		}
		return u;
	};
	auto LCA = [&](int x, int y) -> int {
		if (depth[x] < depth[y]) swap(x, y);
		x = rush(x, depth[x] - depth[y]);
		if (x == y) return x;
		for (int i = Log; i >= 0; i--) {
			if (anc[x][i] != anc[y][i]) {
				x = anc[x][i];
				y = anc[y][i];
			}
		}
		return anc[x][0];
	};
	// end LCA ----------------------------------------------------------------------------
	
	vector<vector<int> > tong(n + 1);
	while (q--) {
		int K;
		cin >> K;
		vector<int> all;
		set<int> st;
		for (int i = 0; i < K; i++) {
			int now;
			cin >> now;
			all.eb(now);
			tong[rdAnc[now]].eb(now);
			st.insert(rdAnc[now]);
		}
		vector<int> vst;
		for (auto x : st) vst.eb(x);
		auto check = [&](int mid) -> bool {
			int flag = 0;
			for (auto nowT : vst) {
				int lca = -1;
				for (auto x : tong[nowT]) {
					if (dis[x] - dis[nowT] <= mid) continue;
					if (lca == -1) lca = x;
					else lca = LCA(lca, x);
				}
				pii p = pii(-INF, -INF);
				for (auto x : tong[nowT]) {
					p.first = max(p.first, dis[x] - dis[nowT]);
					p.second = max(p.second, dis[x] - dis[lca]);
				}
				
				if (p.first <= mid) continue;
				else if (p.second <= mid && flag == 0) {
					flag = 1;
				} else return false;
			}
			return true;
		};
		int l = -1, r = 2e16;
		while (l + 1 < r) {
			int mid = (l + r) >> 1;
			if (check(mid)) r = mid;
			else l = mid;
		}
		cout << r << endl;
		for (auto x : all) {
			tong[rdAnc[x]].clear();
		}
	}
	
	
	return;
}
/*
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

 */
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int T = 1;
	 cin >> T;
	while (T--) {
		run();
	}
	
	
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3492kb

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: 1565ms
memory: 45220kb

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