QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#174954 | #7103. Red Black Tree | mendicillin2# | AC ✓ | 949ms | 21540kb | C++17 | 4.6kb | 2023-09-10 14:51:56 | 2023-09-10 14:51:56 |
Judging History
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