QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#163551 | #7103. Red Black Tree | jrjyy | AC ✓ | 1703ms | 28476kb | C++20 | 4.0kb | 2023-09-04 10:37:26 | 2023-09-04 10:37:26 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n, m, q;
std::cin >> n >> m >> q;
std::vector<bool> red(n);
for (int i = 0; i < m; ++i) {
int x;
std::cin >> x;
--x;
red[x] = true;
}
std::vector<std::vector<std::pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int u, v, w;
std::cin >> u >> v >> w;
--u, --v;
adj[u].emplace_back(v, w), adj[v].emplace_back(u, w);
}
std::vector<int> fa(n, -1);
std::vector<i64> dep(n), top(n);
std::vector<int> dfn(n, -1);
int cur = 0;
auto dfs1 = [&](auto self, int u) -> void {
dfn[u] = cur++;
for (auto [v, w] : adj[u]) {
if (v == fa[u]) {
continue;
}
fa[v] = u, dep[v] = dep[u] + w;
if (!red[v]) {
top[v] = top[u] + w;
}
self(self, v);
}
};
fa[0] = 0;
dfs1(dfs1, 0);
const int lg = std::__lg(n) + 1;
std::vector st(lg + 1, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
st[0][dfn[i]] = fa[i];
}
auto cmp = [&](int x, int y) {
return dfn[x] < dfn[y];
};
for (int i = 0; i < lg; ++i) {
for (int j = 0; j <= n - (2 << i); ++j) {
st[i + 1][j] = std::min(st[i][j], st[i][j + (1 << i)], cmp);
}
}
auto lca = [&](int u, int v) {
if (u == v) {
return u;
}
u = dfn[u], v = dfn[v];
if (u > v) {
std::swap(u, v);
}
int k = std::__lg(v - u++);
return std::min(st[k][u], st[k][v - (1 << k) + 1], cmp);
};
std::vector<int> s;
std::vector<int> idx(n);
std::vector<std::vector<int>> t(n);
std::vector<bool> vis(n);
while (q--) {
int k;
std::cin >> k;
s.resize(k);
for (int i = 0; i < k; ++i) {
std::cin >> s[i];
--s[i];
vis[s[i]] = true;
}
std::sort(s.begin(), s.end(), [&](int x, int y) {
return dfn[x] < dfn[y];
});
for (int i = k - 1; i > 0; --i) {
s.push_back(lca(s[i], s[i - 1]));
}
std::sort(s.begin(), s.end(), [&](int x, int y) {
return dfn[x] < dfn[y];
});
s.erase(std::unique(s.begin(), s.end()), s.end());
for (int i = 0; i < int(s.size()); ++i) {
idx[s[i]] = i;
t[i].clear();
}
for (int i = 1; i < int(s.size()); ++i) {
int f = lca(s[i], s[i - 1]);
t[idx[f]].push_back(i);
}
i64 lo = 0, hi = 1e18;
while (lo < hi) {
i64 m = (lo + hi) / 2;
int cnt = 0;
auto dfs = [&](auto self, int u) -> i64 {
i64 f = -1;
if (vis[s[u]] && !red[s[u]]) {
f = 0;
}
for (auto v : t[u]) {
i64 x = self(self, v);
if (x == -1) {
continue;
}
x += std::min(top[s[v]], dep[s[v]] - dep[s[u]]);
if (x > m) {
cnt += 1;
} else if (dep[s[v]] - dep[s[u]] <= top[s[v]]) {
f = std::max(f, x);
}
}
return f;
};
i64 d = dfs(dfs, 0);
if (d != -1 && d + top[s[0]] > m) {
cnt += 1;
}
if (cnt > 1) {
lo = m + 1;
} else {
hi = m;
}
}
std::cout << lo << '\n';
for (auto x : s) {
vis[x] = false;
}
}
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3824kb
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: 1703ms
memory: 28476kb
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