QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#161518 | #7103. Red Black Tree | ucup-team987# | AC ✓ | 743ms | 22632kb | C++23 | 10.5kb | 2023-09-03 00:15:59 | 2023-09-03 00:15:59 |
Judging History
answer
#if __INCLUDE_LEVEL__ == 0
#include <bits/stdc++.h>
using namespace std;
#include __BASE_FILE__
namespace {
void solve() {
int n, m, q;
cin >> tie(n, m, q);
vector<bool> red(n);
while (m--) {
int i;
cin >> i;
--i;
red[i] = true;
}
HldTree g(n);
for (int _ = n - 1; _--;) {
int i, j, w;
cin >> tie(i, j, w);
--i, --j;
g.add_edge({i, j, w});
}
g.build(0);
vector<int64_t> cost(n);
for (int i : g.order) {
if (!red[i]) {
cost[i] = cost[g.pv[i]] + g.edges[g.pe[i]].cost;
}
}
while (q--) {
int k;
cin >> k;
vector<int> vs(k);
for (int& v : vs) {
cin >> v;
--v;
}
if (k == 1) {
print(0);
continue;
}
ranges::sort(vs, {}, [&](int i) { return cost[i]; });
auto ans = cost[vs.end()[-2]];
int lca = vs.back();
int farthest = vs.back();
for (int t : per(k - 1)) {
int v = vs[t];
lca = g.lca(lca, v);
if (g.distance(lca, farthest) < g.distance(lca, v)) {
farthest = v;
}
chmin(ans, max(t ? cost[vs[t - 1]] : 0, g.distance(lca, farthest)));
}
print(ans);
}
}
} // namespace
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
#else // __INCLUDE_LEVEL__
template <class T, class U = T>
bool chmin(T& x, U&& y) {
return y < x && (x = forward<U>(y), true);
}
template <class T, class U = T>
bool chmax(T& x, U&& y) {
return x < y && (x = forward<U>(y), true);
}
namespace std {
template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
return is >> p.first >> p.second;
}
template <class... Ts>
istream& operator>>(istream& is, tuple<Ts...>& t) {
return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t);
}
template <class... Ts>
istream& operator>>(istream& is, tuple<Ts&...>&& t) {
return is >> t;
}
template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr>
auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) {
for (auto&& e : r) {
is >> e;
}
return is;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << p.first << ' ' << p.second;
}
template <class... Ts>
ostream& operator<<(ostream& os, const tuple<Ts...>& t) {
auto f = [&os](const auto&... xs) -> ostream& {
[[maybe_unused]] auto sep = "";
((os << exchange(sep, " ") << xs), ...);
return os;
};
return apply(f, t);
}
template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr>
auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) {
auto sep = "";
for (auto&& e : r) {
os << exchange(sep, " ") << e;
}
return os;
}
} // namespace std
template <class... Ts>
void print(Ts&&... xs) {
cout << tie(xs...) << '\n';
}
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
struct Graph {
struct Edge {
int src, dst;
int64_t cost;
int other(int v) const {
__glibcxx_assert(v == src or v == dst);
return src ^ dst ^ v;
}
};
std::vector<Edge> edges;
std::vector<std::vector<std::pair<int, int>>> adj;
Graph() {}
explicit Graph(int n) : adj(n) {}
int n() const { return std::size(adj); }
int m() const { return std::size(edges); }
int add_edge(const Edge& e, bool directed) {
__glibcxx_assert(0 <= e.src and e.src < n());
__glibcxx_assert(0 <= e.dst and e.dst < n());
int id = m();
edges.push_back(e);
adj[e.src].emplace_back(e.dst, id);
if (not directed) adj[e.dst].emplace_back(e.src, id);
return id;
}
};
struct DfsTree : Graph {
using T = decltype(Edge::cost);
std::vector<int> root;
std::vector<int> pv;
std::vector<int> pe;
std::vector<int> order;
std::vector<int> in;
std::vector<int> out;
std::vector<int> sub;
std::vector<int> depth;
std::vector<int> min_depth;
std::vector<T> dist;
std::vector<int> last;
int num_trials;
DfsTree() {}
explicit DfsTree(int n)
: Graph(n),
root(n, -1),
pv(n, -1),
pe(n, -1),
in(n, -1),
out(n, -1),
sub(n, -1),
depth(n, -1),
min_depth(n, -1),
dist(n, std::numeric_limits<T>::max()),
last(n, -1),
num_trials(0) {}
int add_edge(const Edge& e) { return Graph::add_edge(e, false); }
void dfs(int r, bool clear_order = true) {
__glibcxx_assert(0 <= r and r < n());
root[r] = r;
pv[r] = -1;
pe[r] = -1;
if (clear_order) order.clear();
depth[r] = 0;
dist[r] = T{};
dfs_impl(r);
++num_trials;
}
void dfs_all() {
std::fill(std::begin(root), std::end(root), -1);
for (int v = 0; v < n(); ++v)
if (root[v] == -1) dfs(v, v == 0);
}
int deeper(int id) const {
__glibcxx_assert(0 <= id and id < m());
int a = edges[id].src;
int b = edges[id].dst;
return depth[a] < depth[b] ? b : a;
}
bool is_tree_edge(int id) const {
__glibcxx_assert(0 <= id and id < m());
return id == pe[deeper(id)];
}
bool is_ancestor(int u, int v) const {
__glibcxx_assert(0 <= u and u < n());
__glibcxx_assert(0 <= v and v < n());
return in[u] <= in[v] and out[v] <= out[u];
}
private:
void dfs_impl(int v) {
in[v] = std::size(order);
order.push_back(v);
sub[v] = 1;
min_depth[v] = depth[v];
last[v] = num_trials;
for (auto&& [u, id] : adj[v]) {
if (id == pe[v]) continue;
if (last[u] == num_trials) {
min_depth[v] = std::min(min_depth[v], depth[u]);
continue;
}
root[u] = root[v];
pv[u] = v;
pe[u] = id;
depth[u] = depth[v] + 1;
dist[u] = dist[v] + edges[id].cost;
dfs_impl(u);
sub[v] += sub[u];
min_depth[v] = std::min(min_depth[v], min_depth[u]);
}
out[v] = std::size(order);
}
};
struct HldTree : DfsTree {
std::vector<int> head;
HldTree() {}
explicit HldTree(int n) : DfsTree(n), head(n, -1) {}
void build(int r, bool clear_order = true) {
__glibcxx_assert(0 <= r and r < n());
dfs(r, clear_order);
order.erase(std::end(order) - sub[r], std::end(order));
head[r] = r;
build_impl(r);
}
void build_all() {
std::fill(std::begin(root), std::end(root), -1);
for (int v = 0; v < n(); ++v)
if (root[v] == -1) build(v, v == 0);
}
int lca(int u, int v) const {
__glibcxx_assert(0 <= u and u < n());
__glibcxx_assert(0 <= v and v < n());
__glibcxx_assert(root[u] == root[v]);
while (true) {
if (in[u] > in[v]) std::swap(u, v);
if (head[u] == head[v]) return u;
v = pv[head[v]];
}
}
int d(int u, int v) const {
__glibcxx_assert(0 <= u and u < n());
__glibcxx_assert(0 <= v and v < n());
__glibcxx_assert(root[u] == root[v]);
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
T distance(int u, int v) const {
__glibcxx_assert(0 <= u and u < n());
__glibcxx_assert(0 <= v and v < n());
__glibcxx_assert(root[u] == root[v]);
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
int la(int v, int d) const {
__glibcxx_assert(0 <= v and v < n());
__glibcxx_assert(0 <= d and d <= depth[v]);
while (depth[head[v]] > d) v = pv[head[v]];
return order[in[head[v]] + (d - depth[head[v]])];
}
int next(int src, int dst) const {
__glibcxx_assert(0 <= src and src < n());
__glibcxx_assert(0 <= dst and dst < n());
__glibcxx_assert(root[src] == root[dst]);
__glibcxx_assert(src != dst);
if (not is_ancestor(src, dst)) return pv[src];
return la(dst, depth[src] + 1);
}
int next(int src, int dst, int k) const {
__glibcxx_assert(0 <= src and src < n());
__glibcxx_assert(0 <= dst and dst < n());
__glibcxx_assert(root[src] == root[dst]);
__glibcxx_assert(k >= 0);
int v = lca(src, dst);
if (k <= depth[src] - depth[v]) return la(src, depth[src] - k);
k -= depth[src] - depth[v];
__glibcxx_assert(k <= depth[dst] - depth[v]);
return la(dst, depth[v] + k);
}
template <class Function>
void apply(int src, int dst, bool vertex, Function f) const {
__glibcxx_assert(0 <= src and src < n());
__glibcxx_assert(0 <= dst and dst < n());
__glibcxx_assert(root[src] == root[dst]);
int v = lca(src, dst);
while (head[src] != head[v]) {
f(in[src] + 1, in[head[src]]);
src = pv[head[src]];
}
if (vertex)
f(in[src] + 1, in[v]);
else if (src != v)
f(in[src] + 1, in[v] + 1);
auto rec = [&](auto self, int to) -> void {
if (head[v] == head[to]) {
if (v != to) f(in[v] + 1, in[to] + 1);
return;
}
self(self, pv[head[to]]);
f(in[head[to]], in[to] + 1);
};
rec(rec, dst);
}
template <class Searcher>
int search(int src, int dst, bool vertex, Searcher f) const {
__glibcxx_assert(0 <= src and src < n());
__glibcxx_assert(0 <= dst and dst < n());
__glibcxx_assert(root[src] == root[dst]);
int res = -1;
apply(src, dst, vertex, [&](int l, int r) {
if (res != -1) return;
int i = f(l, r);
if (l > r) std::swap(l, r);
if (l <= i and i < r) res = vertex ? order[i] : pe[order[i]];
});
return res;
}
private:
void build_impl(int v) {
in[v] = std::size(order);
order.push_back(v);
auto pos =
std::partition(std::begin(adj[v]), std::end(adj[v]),
[&](auto&& e) { return e.second == pe[e.first]; });
auto it = std::max_element(
std::begin(adj[v]), pos,
[&](auto&& a, auto&& b) { return sub[a.first] < sub[b.first]; });
if (it != std::begin(adj[v])) std::iter_swap(std::begin(adj[v]), it);
std::partition(pos, std::end(adj[v]),
[&](auto&& e) { return e.second == pe[v]; });
for (auto&& [u, id] : adj[v]) {
if (id != pe[u]) break;
head[u] = u == adj[v].front().first ? head[v] : u;
build_impl(u);
}
out[v] = std::size(order);
}
};
#endif // __INCLUDE_LEVEL__
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3892kb
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: 743ms
memory: 22632kb
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