QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#158451 | #7103. Red Black Tree | ucup-team133# | AC ✓ | 1506ms | 30944kb | C++23 | 5.4kb | 2023-09-02 16:32:42 | 2023-09-02 16:32:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct HeavyLightDecomposition {
vector<vector<pair<int, int>>> G;
int n, time;
vector<int> par, sub, head, vid;
vector<ll> dep;
HeavyLightDecomposition(int n) : G(n), n(n), time(0), par(n, -1), sub(n), head(n), vid(n, -1), dep(n) {}
void add_edge(int u, int v, int w) {
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
void build() {
dfs_sz(0);
head[0] = 0;
dfs_hld(0);
}
int lca(int u, int v) {
for (;; v = par[head[v]]) {
if (vid[u] > vid[v]) swap(u, v);
if (head[u] == head[v]) return u;
}
}
pair<unordered_map<int, vector<int>>, int> virtualtree(vector<int>& vs) {
int sz = vs.size();
sort(begin(vs), end(vs), [&](int i, int j) { return vid[i] < vid[j]; });
for (int i = 0; i < sz - 1; i++) vs.emplace_back(lca(vs[i], vs[i + 1]));
sort(begin(vs), end(vs), [&](int i, int j) { return vid[i] < vid[j]; });
vs.erase(unique(begin(vs), end(vs)), end(vs));
vector<int> s;
unordered_map<int, vector<int>> res;
for (int v : vs) {
while (not s.empty() and vid[s.back()] + sub[s.back()] <= vid[v]) s.pop_back();
if (not s.empty()) res[s.back()].emplace_back(v);
s.emplace_back(v);
}
return {res, vs[0]};
}
private:
void dfs_sz(int v) {
sub[v] = 1;
if (not G[v].empty() and G[v].front().first == par[v]) swap(G[v].front(), G[v].back());
for (auto& p : G[v]) {
int u = p.first;
if (u == par[v]) continue;
par[u] = v;
dep[u] = dep[v] + p.second;
dfs_sz(u);
sub[v] += sub[u];
if (sub[u] > sub[G[v].front().first]) swap(p, G[v].front());
}
}
void dfs_hld(int v) {
vid[v] = time++;
for (auto& p : G[v]) {
int u = p.first;
if (u == par[v]) continue;
head[u] = (u == G[v][0].first ? head[v] : u);
dfs_hld(u);
}
}
};
constexpr ll INF = (1LL << 60) - 1;
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<bool> red(n, false);
for (; m--;) {
int v;
cin >> v;
red[--v] = true;
}
HeavyLightDecomposition HLD(n);
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
HLD.add_edge(--u, --v, w);
}
HLD.build();
vector<bool> target(n, false);
vector<ll> nxt(n); // v の祖先であって最も近い赤までの距離
auto& G = HLD.G;
{
auto dfs = [&](auto self, int v, int p, ll D) -> void {
if (red[v]) D = 0;
nxt[v] = D;
for (auto [u, w] : G[v]) {
if (u == p) continue;
self(self, u, v, D + w);
}
};
dfs(dfs, 0, -1, 0);
}
vector dp(n, vector<ll>(3, -INF));
auto query = [&](vector<int> vs) -> ll {
auto nvs = vs;
if (nvs.front() != 0) nvs.insert(nvs.begin(), 0);
auto [g, root] = HLD.virtualtree(nvs);
for (int& v : vs) target[v] = true;
auto dfs1 = [&](auto self, int v) -> void {
for (int u : g[v]) {
self(self, u);
ll w = HLD.dep[u] - HLD.dep[v];
dp[v][1] = max(dp[v][1], dp[u][1]);
ll x = nxt[u];
if (dp[u][0] >= 0 and x <= w)
dp[v][1] = max(dp[v][1], dp[u][0] + x);
else
dp[v][0] = max(dp[v][0], dp[u][0] + (dp[u][0] >= 0 ? w : 0));
dp[v][2] = max(dp[v][2], dp[u][2]);
}
if (target[v]) {
dp[v][0] = max(dp[v][0], 0LL);
dp[v][2] = max(dp[v][2], nxt[v]);
}
if (red[v]) {
dp[v][1] = max(dp[v][1], dp[v][0]);
dp[v][0] = -INF;
}
};
dfs1(dfs1, root);
ll ans = dp[root][2];
auto dfs2 = [&](auto self, int v, ll D) -> void {
vector<ll> vals;
auto& ch = g[v];
ans = min(ans, max({dp[v][0], dp[v][1], D}));
if (target[v]) D = max(D, nxt[v]);
int len = ch.size() + 1;
for (int i = 0; i < len - 1; i++) vals.emplace_back(dp[ch[i]][2]);
vals.emplace_back(D);
vector<ll> left(len + 1), right(len + 1);
left[0] = right[len] = -INF;
for (int i = 0; i < len; i++) left[i + 1] = max(left[i], vals[i]);
for (int i = len - 1; i >= 0; i--) right[i] = max(right[i + 1], vals[i]);
for (int i = 0; i < len - 1; i++) self(self, ch[i], max(left[i], right[i + 1]));
};
dfs2(dfs2, root, -INF);
for (int& v : vs) target[v] = false;
for (int& v : nvs) {
for (int i = 0; i < 3; i++) {
dp[v][i] = -INF;
}
}
return ans;
};
for (; q--;) {
int k;
cin >> k;
vector<int> vs(k);
for (int& v : vs) cin >> v, v--;
cout << query(vs) << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (; T--;) solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3676kb
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: 1506ms
memory: 30944kb
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