QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#158343 | #7103. Red Black Tree | ucup-team1055# | AC ✓ | 1130ms | 52320kb | C++17 | 6.2kb | 2023-09-02 16:26:40 | 2023-09-02 16:26:41 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,n) for(int i = int(s); i < int(n); i++)
#define rrep(i,s,n) for(int i = int(n) - 1; i >= int(s); i--)
#define all(v) (v).begin(), (v).end()
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<class T>
void debug(const T &a) {
std::cerr << "[debug]" << a << std::endl;
}
template<typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &a) {
rep(i,0,a.size()) {
os << a[i] << (i + 1 == (int)a.size() ? "" : " ");
}
return os;
}
template<class T>
bool chmin(T &a, T b) {
if(a <= b) return false;
a = b;
return true;
}
template<class T>
bool chmax(T &a, T b) {
if(a >= b) return false;
a = b;
return true;
}
template<class Band, Band (*op)(Band, Band)>
struct sparse_table {
public:
sparse_table() = default;
void build(const std::vector<Band> &a) {
n = (int)a.size();
table = std::vector(std::__lg(n) + 1, std::vector<Band>(n));
for(int i = 0; i < n; i++) {
table[0][i] = a[i];
}
for(int k = 1; (1<<k) <= n; k++) {
for(int i = 0; i + (1 << k) <= n; i++) {
table[k][i] = op(table[k-1][i], table[k-1][i + (1<<(k-1))]);
}
}
}
Band fold(int l, int r) {
int k = std::__lg(r - l);
return op(table[k][l], table[k][r - (1<<k)]);
}
private:
int n;
std::vector<std::vector<Band>> table;
};
std::pair<int,int> op(std::pair<int,int> lhs, std::pair<int,int> rhs) {
return lhs.second < rhs.second ? lhs : rhs;
}
void solve() {
int n,m,q;
std::cin >> n >> m >> q;
std::vector tree(n, std::vector<std::pair<int,ll>>());
std::vector<int> color(n, 0);
rep(i,0,m) {
int r;
std::cin >> r;
r--;
color[r] = 1;
}
rep(i,0,n-1) {
int u, v;
ll w;
std::cin >> u >> v >> w;
u--; v--;
tree[u].emplace_back(v, w);
tree[v].emplace_back(u, w);
}
std::vector<int> in, out;
std::vector<int> id(n);
std::vector<int> cnt(n, 0);
std::vector<std::pair<int,int>> vs;
std::vector<ll> dist(n, 0);
std::vector<ll> cost(n);
{
auto euler_tour_dfs = [&](auto &&self, int v, int par, int d, ll red) -> void {
id[v] = int(vs.size());
vs.emplace_back(v, d);
if(color[v] == 1) chmax(red, dist[v]);
cost[v] = dist[v] - red;
if(color[v] == 1) cnt[v]++;
for(auto [nv, w]: tree[v]) {
if(nv == par) continue;
dist[nv] = dist[v] + w;
cnt[nv] = cnt[v];
self(self, nv, v, d + 1, red);
vs.emplace_back(v, d);
}
};
euler_tour_dfs(euler_tour_dfs, 0, -1, 0, 0);
}
sparse_table<std::pair<int,int>, op> st;
st.build(vs);
auto lca = [&](int u, int v) -> int {
u = id[u];
v = id[v];
if(u > v) std::swap(u, v);
return st.fold(u, v + 1).first;
};
std::vector<int> rev(n, -1), mark(n, -1);
while(q--) {
int k;
std::cin >> k;
std::vector<int> vk(k);
for(auto &v: vk) {
std::cin >> v;
v--;
assert(0 <= v && v < n);
mark[v] = 1;
}
std::vector<int> s;
std::vector<std::vector<int>> auxiliary_tree;
int sz;
std::vector<ll> cost_a;
{
std::sort(all(vk), [&](int u, int v) -> bool { return id[u] < id[v]; });
s = vk;
rep(i,0,k-1) {
s.emplace_back(lca(vk[i], vk[i+1]));
}
s.emplace_back(0);
std::sort(all(s), [&](int u, int v) -> bool { return id[u] < id[v]; });
s.erase(std::unique(all(s)), s.end());
sz = s.size();
auxiliary_tree.resize(sz);
cost_a.resize(sz);
rep(i,0,sz) {
int v = s[i];
rev[v] = i;
if(mark[v] > 0) cost_a[i] = cost[v];
}
rep(i,0,sz-1) {
int l = lca(s[i], s[i+1]);
int u = rev[l];
int v = rev[s[i+1]];
auxiliary_tree[u].emplace_back(v);
auxiliary_tree[v].emplace_back(u);
}
}
int root = rev[0];
std::vector<int> in(sz), out(sz);
{
int t = 0;
auto euler_tour_dfs = [&](auto &&self, int v, int par = -1) -> void {
in[v] = t++;
for(auto nv: auxiliary_tree[v]) {
if(nv == par) continue;
self(self, nv, v);
}
out[v] = t;
};
euler_tour_dfs(euler_tour_dfs, root);
}
std::vector<ll> left_max(sz+1, 0), right_max(sz+1, 0);
rep(i,0,sz) {
left_max[i+1] = right_max[i] = cost_a[in[i]];
}
rep(i,0,sz) {
chmax(left_max[i+1], left_max[i]);
}
rrep(i,0,sz) {
chmax(right_max[i], right_max[i+1]);
}
ll ans = std::numeric_limits<ll>::max();
auto dfs = [&](auto &&self, int v, int par = -1) -> std::tuple<ll,ll,ll> {
ll a = dist[s[v]], b = 0, c = cost_a[v];
for(auto nv: auxiliary_tree[v]) {
if(nv == par) continue;
auto [s_a, s_b, s_c] = self(self, nv, v);
if(cnt[s[nv]] - cnt[s[v]] > 0) {
s_a = 0;
s_b = s_c;
}
chmax(a, s_a);
chmax(b, s_b);
chmax(c, s_c);
}
ll ret = std::max(a - dist[s[v]], b);
chmax(ret, left_max[in[v]]);
chmax(ret, right_max[out[v]]);
chmin(ans, ret);
return {a, b, c};
};
dfs(dfs, root);
std::cout << ans << '\n';
for(auto v: vk) mark[v] = -1;
}
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int t;
std::cin >> t;
while(t--) {
solve();
}
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3680kb
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: 1130ms
memory: 52320kb
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