QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#174954#7103. Red Black Treemendicillin2#AC ✓949ms21540kbC++174.6kb2023-09-10 14:51:562023-09-10 14:51:56

Judging History

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

  • [2023-09-10 14:51:56]
  • 评测
  • 测评结果:AC
  • 用时:949ms
  • 内存:21540kb
  • [2023-09-10 14:51:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
using uint = uint32_t;
using ull = uint64_t;

mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

template <class F>
struct ycr {
	F f;
	template <class T> explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args> decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F> decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

struct hldecomp {
	int n;
	vi ord;
	vc<array<int, 2>> idx;
	vc<pair<int, int>> heavy;
	hldecomp(const vi& par) : n(sz(par)), ord(n), idx(n), heavy(n) {
		vvc<int> ch(n);
		for (int i = 0; i < n; i++) {
			if (par[i] != -1) {
				ch[par[i]].push_back(i);
			}
		}
		vi s(n);
		int nidx = 0;
		for (int i = 0; i < n; i++) {
			if (par[i] != -1) continue;
			yc([&](auto self, int v) -> void {
				s[v] = 1;
				for (int w : ch[v]) {
					self(w);
					s[v] += s[w];
				}
				if (!ch[v].empty()) {
					auto mit = max_element(ch[v].begin(), ch[v].end(), [&](int a, int b) {
						return s[a] < s[b];
					});
					swap(*ch[v].begin(), *mit);
				}
			})(i);
			yc([&](auto self, int v, bool rt = true) -> void {
				ord[idx[v][0] = nidx++] = v;
				if (rt) {
					heavy[idx[v][0]] = {par[v] == -1 ? -1 : idx[par[v]][0], 1};
				} else {
					assert(idx[par[v]][0] == idx[v][0]-1);
					heavy[idx[v][0]] = heavy[idx[v][0]-1];
					heavy[idx[v][0]].second++;
				}
				bool crt = false;
				for (int w : ch[v]) {
					self(w, crt);
					crt = true;
				}
				idx[v][1] = nidx;
			})(i);
		}
	}

	int get_ancestor(int a, int k) {
		assert(k >= 0);
		a = idx[a][0];
		while (a != -1 && k) {
			if (k >= heavy[a].second) {
				k -= heavy[a].second;
				assert(heavy[a].first <= a - heavy[a].second);
				a = heavy[a].first;
			} else {
				a -= k;
				k = 0;
			}
		}
		if (a == -1) return -1;
		else return ord[a];
	}

	int lca(int a, int b) {
		a = idx[a][0], b = idx[b][0];
		while (true) {
			if (a > b) swap(a, b);
			assert(a <= b);
			if (a > b - heavy[b].second) {
				return ord[a];
			}
			b = heavy[b].first;
			if (b == -1) return -1;
		}
	}
};

template <class T> void setmax(T& a, const T& b) {
	if (a < b) a = b;
}
template <class T> void setmin(T& a, const T& b) {
	if (a > b) a = b;
}

void solve() {
	int N, M, Q; cin >> N >> M >> Q;

	vector<bool> red(N);
	for (int j = 0; j < M; j++) {
		int v; cin >> v; v--;
		red[v] = true;
	}
	assert(red[0]);

	vector<vector<pair<int, int>>> adj(N);
	for (int e = 0; e < N-1; e++) {
		int u, v, w; cin >> u >> v >> w; u--, v--;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}

	vector<int> par(N);
	vector<ll> root_dist(N);
	vector<ll> init_cost(N);
	{
		yc([&](auto self, int cur, int prv, ll nearest) -> void {
			if (red[cur]) {
				nearest = 0;
			} else {
				init_cost[cur] = nearest;
			}
			par[cur] = prv;
			for (auto [nxt, x] : adj[cur]) {
				if (nxt == prv) continue;
				root_dist[nxt] = root_dist[cur] + x;
				self(nxt, cur, nearest + x);
			}
		})(0, -1, 0);
		assert(par[0] == -1);
	}

	hldecomp hld(par);
	const auto& idx = hld.idx;

	vector<bool> chosen(N, false);
	for (int q = 0; q < Q; q++) {
		int K; cin >> K;
		vector<int> vs(K);
		for (int& v : vs) {
			cin >> v; v--;
		}

		auto cmp = [&](int a, int b) -> bool {
			return idx[a][0] < idx[b][0];
		};
		sort(vs.begin(), vs.end(), cmp);
		const int V = int(vs.size());
		assert(V >= 1);
		vector<int> adjacent_lca(V-1);
		for (int i = 0; i < V-1; i++) {
			adjacent_lca[i] = hld.lca(vs[i], vs[i+1]);
		}

		//cerr << "HELLO" << endl;

		ll max_cost = 0;
		for (const int& v : vs) {
			setmax(max_cost, init_cost[v]);
		}
		ll mi = -1;
		ll ma = max_cost;
		while (ma - mi > 1) {
			ll md = (mi + ma) / 2;
			//assert(md <= max_cost);
			if (md < max_cost) {
				int st = 0;
				while (init_cost[vs[st]] <= md) st++;
				int en = V;
				while (init_cost[vs[en-1]] <= md) en--;
				ll min_dist = root_dist[vs[st]];
				ll max_dist = root_dist[vs[st]];
				for (int j = st; j < en; j++) {
					const int& v = vs[j];
					if (init_cost[v] > md) {
						setmax(max_dist, root_dist[vs[j]]);
					}
					if (j+1 < en) {
						setmin(min_dist, root_dist[adjacent_lca[j]]);
					}
				}
				if (max_dist - min_dist <= md) {
					ma = md;
				} else {
					mi = md;
				}
			} else {
				ma = md;
			}
		}
		cout << ma << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);

	int T; cin >> T;
	while (T--) solve();
}

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

详细

Test #1:

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

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: 949ms
memory: 21540kb

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