QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#159305 | #7103. Red Black Tree | ucup-team1631# | AC ✓ | 1503ms | 42976kb | C++20 | 6.4kb | 2023-09-02 17:45:35 | 2023-09-02 17:45:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
return a > b ? (a = b, 1) : 0;
}
class LCA {
public:
LCA() = default;
LCA(const std::vector<std::vector<int>>& G, int root)
: G(G), LOG(32 - __builtin_clz(G.size())), depth(G.size()) {
int V = G.size();
table.assign(LOG, std::vector<int>(V, -1));
dfs(root, -1, 0);
for (int k = 0; k < LOG - 1; ++k) {
for (int v = 0; v < V; ++v) {
if (table[k][v] >= 0) {
table[k + 1][v] = table[k][table[k][v]];
}
}
}
}
int query(int u, int v) const {
if (depth[u] > depth[v]) std::swap(u, v);
// go up to the same depth
for (int k = 0; k < LOG; ++k) {
if ((depth[v] - depth[u]) >> k & 1) {
v = table[k][v];
}
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (table[k][u] != table[k][v]) {
u = table[k][u];
v = table[k][v];
}
}
return table[0][u];
}
int dist(int u, int v) const {
return depth[u] + depth[v] - 2 * depth[query(u, v)];
}
int parent(int v, int k) const {
for (int i = LOG - 1; i >= 0; --i) {
if (k >= (1 << i)) {
v = table[i][v];
k -= 1 << i;
}
}
return v;
}
int jump(int u, int v, int k) const {
int l = query(u, v);
int du = depth[u] - depth[l];
int dv = depth[v] - depth[l];
if (du + dv < k) return -1;
if (k < du) return parent(u, k);
return parent(v, du + dv - k);
}
protected:
const std::vector<std::vector<int>>& G;
const int LOG;
std::vector<std::vector<int>> table;
std::vector<int> depth;
void dfs(int v, int p, int d) {
table[0][v] = p;
depth[v] = d;
for (int c : G[v]) {
if (c != p) dfs(c, v, d + 1);
}
}
};
template <typename M>
class BinaryLifting : public LCA {
using T = typename M::T;
public:
BinaryLifting() = default;
BinaryLifting(const std::vector<std::vector<int>>& G,
const std::vector<T> vs, int root)
: LCA(G, root) {
int V = G.size();
val.assign(LOG, std::vector<int>(V, M::id()));
val[0] = vs;
for (int k = 0; k < LOG - 1; ++k) {
for (int v = 0; v < V; ++v) {
if (table[k][v] >= 0) {
val[k + 1][v] = M::op(val[k][v], val[k][table[k][v]]);
}
}
}
}
T fold(int u, int v) const {
bool flipped = false;
if (depth[u] > depth[v]) {
std::swap(u, v);
flipped = true;
}
T resu = M::id(), resv = M::id();
// go up to the same depth
for (int k = 0; k < LOG; ++k) {
if ((depth[v] - depth[u]) >> k & 1) {
resv = M::op(resv, val[k][v]);
v = table[k][v];
}
}
if (u == v) {
resu = M::op(val[0][u], M::flip(resv));
if (flipped) resu = M::flip(resu);
return resu;
}
for (int k = LOG - 1; k >= 0; --k) {
if (table[k][u] != table[k][v]) {
resu = M::op(resu, val[k][u]);
resv = M::op(resv, val[k][v]);
u = table[k][u];
v = table[k][v];
}
}
resu = M::op(M::op(resu, val[0][table[0][u]]), M::flip(resv));
if (flipped) resu = M::flip(resu);
return resu;
}
private:
std::vector<std::vector<T>> val;
};
struct AddMonoid {
using T = int;
static T id() { return 0; }
static T op(T a, T b) { return a + b; }
static T flip(T x) { return x; }
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int T;
cin >> T;
while (T--) {
int n, m, q;
cin >> n >> m >> q;
vector<int> red(n);
rep(i, 0, m) {
int r;
cin >> r;
--r;
red[r] = 1;
}
vector<vector<pair<int, ll>>> G(n);
vector<vector<int>> tree(n);
rep(_, 0, n - 1) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
G[u].push_back({v, w});
G[v].push_back({u, w});
tree[u].push_back(v);
tree[v].push_back(u);
}
// calculate the distance to the nearest red ancestor
vector<ll> cost(n);
auto dfs = [&](auto& dfs, int v, int p, ll x) -> void {
if (red[v]) x = 0;
cost[v] = x;
for (auto [c, w] : G[v]) {
if (c == p) continue;
dfs(dfs, c, v, x + w);
}
};
dfs(dfs, 0, -1, 0);
LCA lca(tree, 0);
BinaryLifting<AddMonoid> bl(tree, red, 0);
while (q--) {
int k;
cin >> k;
vector<pair<ll, int>> vs(k);
rep(i, 0, k) {
int v;
cin >> v;
--v;
vs[i] = {cost[v], v};
}
// process in the descending order of the current cost
sort(all(vs));
reverse(all(vs));
vs.push_back({0, -1});
ll ans = vs[0].first;
int l = vs[0].second;
rep(i, 0, k) {
auto [c, v] = vs[i];
int nl = lca.query(l, v);
// check if nl can become the nearest red for all v
if (bl.fold(nl, l) + bl.fold(nl,v) > 0) {
break;
}
l = nl;
chmin(ans, max(vs[0].first - cost[l], vs[i + 1].first));
}
cout << ans << "\n";
}
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
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: 1503ms
memory: 42976kb
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