QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#160364 | #7103. Red Black Tree | ucup-team1469# | AC ✓ | 1251ms | 24368kb | C++17 | 16.2kb | 2023-09-02 20:15:53 | 2023-09-02 20:15:53 |
Judging History
answer
#ifndef LOCAL
#define FAST_IO
#endif
// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
template <typename T>
using Vec = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
istream &operator>>(istream &is, i128 &x) {
i64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, i128 x) {
os << (i64)x;
return os;
}
istream &operator>>(istream &is, u128 &x) {
u64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, u128 x) {
os << (u64)x;
return os;
}
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
// ============
#ifdef DEBUGF
#else
#define DBG(x) (void)0
#endif
// ============
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
class HeavyLightDecomposition {
std::vector<int> siz;
std::vector<int> par;
std::vector<int> hea;
std::vector<int> in;
std::vector<int> out;
std::vector<int> dep;
std::vector<int> rev;
template <typename G>
void dfs1(G &g, int v) {
if (!g[v].empty() && (int) g[v][0] == par[v]) {
std::swap(g[v][0], g[v].back());
}
for (auto &e : g[v]) {
int u = (int)e;
if (u != par[v]) {
par[u] = v;
dfs1(g, u);
siz[v] += siz[u];
if (siz[u] > siz[(int) g[v][0]]) {
std::swap(g[v][0], e);
}
}
}
}
template <typename G>
void dfs2(const G &g, int v, int &time) {
in[v] = time;
rev[time++] = v;
for (auto &e : g[v]) {
int u = (int)e;
if (u == par[v]) {
continue;
}
if (u == (int) g[v][0]) {
hea[u] = hea[v];
} else {
hea[u] = u;
}
dep[u] = dep[v] + 1;
dfs2(g, u, time);
}
out[v] = time;
}
public:
template <typename G>
HeavyLightDecomposition(G &g, int root = 0) :
siz(g.size(), 1),
par(g.size(), root),
hea(g.size(), root),
in(g.size(), 0),
out(g.size(), 0),
dep(g.size(), 0),
rev(g.size(), 0) {
assert(root >= 0 && root < (int) g.size());
dfs1(g, root);
int time = 0;
dfs2(g, root, time);
}
int subtree_size(int v) const {
assert(v >= 0 && v < (int) siz.size());
return siz[v];
}
int parent(int v) const {
assert(v >= 0 && v < (int) par.size());
return par[v];
}
int in_time(int v) const {
assert(v >= 0 && v < (int) in.size());
return in[v];
}
int out_time(int v) const {
assert(v >= 0 && v < (int) out.size());
return out[v];
}
int depth(int v) const {
assert(v >= 0 && v < (int) dep.size());
return dep[v];
}
int time_to_vertex(int t) const {
assert(t >= 0 && t < (int) rev.size());
return rev[t];
}
int la(int v, int k) const {
assert(v >= 0 && v < (int) dep.size());
assert(k >= 0);
if (k > dep[v]) {
return -1;
}
while (true) {
int u = hea[v];
if (in[u] + k <= in[v]) {
return rev[in[v] - k];
}
k -= in[v] - in[u] + 1;
v = par[u];
}
return 0;
}
int forward(int v, int dst) const {
assert(v >= 0 && v < (int) dep.size());
assert(dst >= 0 && dst < (int) dep.size());
assert(v != dst);
int l = lca(v, dst);
if (l == v) {
return la(dst, dep[dst] - dep[v] - 1);
} else {
return par[v];
}
}
int lca(int u, int v) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
while (u != v) {
if (in[u] > in[v]) {
std::swap(u, v);
}
if (hea[u] == hea[v]) {
v = u;
} else {
v = par[hea[v]];
}
}
return u;
}
int dist(int u, int v) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
std::vector<std::pair<int, int>> path(int u, int v, bool edge) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
std::vector<std::pair<int, int>> fromu, fromv;
bool rev = false;
while (true) {
if (u == v && edge) {
break;
}
if (in[u] > in[v]) {
std::swap(u, v);
std::swap(fromu, fromv);
rev ^= true;
}
if (hea[u] == hea[v]) {
fromv.emplace_back(in[v], in[u] + (int)edge);
v = u;
break;
} else {
fromv.emplace_back(in[v], in[hea[v]]);
v = par[hea[v]];
}
}
if (rev) {
std::swap(fromu, fromv);
}
std::reverse(fromv.begin(), fromv.end());
fromu.reserve(fromv.size());
for (auto [x, y] : fromv) {
fromu.emplace_back(y, x);
}
return fromu;
}
int jump(int u, int v, int k) const {
assert(u >= 0 && u < (int) dep.size());
assert(v >= 0 && v < (int) dep.size());
assert(k >= 0);
int l = lca(u, v);
int dis = dep[u] + dep[v] - 2 * dep[l];
if (k > dis) {
return -1;
}
if (k <= dep[u] - dep[l]) {
return la(u, k);
} else {
return la(v, dis - k);
}
}
int meet(int u, int v, int w) const {
return lca(u, v) ^ lca(v, w) ^ lca(w, u);
}
};
// ============
// ============
#include <utility>
#include <vector>
#include <numeric>
#include <cassert>
template <typename Edge>
class Graph {
std::vector<std::vector<Edge>> edges;
public:
Graph() : edges() {}
Graph(int v) : edges(v) {
assert(v >= 0);
}
std::vector<int> add_vertices(int n) {
int v = (int) edges.size();
std::vector<int> idx(n);
std::iota(idx.begin(), idx.end(), v);
edges.resize(edges.size() + n);
return idx;
}
template <typename... T>
void add_directed_edge(int from, int to, T &&...val) {
assert(from >= 0 && from < (int) edges.size());
assert(to >= 0 && to < (int) edges.size());
edges[from].emplace_back(Edge(to, std::forward<T>(val)...));
}
template <typename... T>
void add_undirected_edge(int u, int v, const T &...val) {
assert(u >= 0 && u < (int) edges.size());
assert(v >= 0 && v < (int) edges.size());
edges[u].emplace_back(Edge(v, val...));
edges[v].emplace_back(Edge(u, val...));
}
int size() const {
return (int) edges.size();
}
const std::vector<Edge> &operator[](int v) const {
assert(v >= 0 && v < (int) edges.size());
return edges[v];
}
std::vector<Edge> &operator[](int v) {
assert(v >= 0 && v < (int) edges.size());
return edges[v];
}
};
struct UnweightedEdge {
int to;
UnweightedEdge(int t) : to(t) {}
explicit operator int() const {
return to;
}
using Weight = int;
Weight weight() const {
return 1;
}
};
template <typename T>
struct WeightedEdge {
int to;
T wt;
WeightedEdge(int t, const T &w) : to(t), wt(w) {}
explicit operator int() const {
return to;
}
using Weight = T;
Weight weight() const {
return wt;
}
};
// ============
void solve() {
i32 n, m, q;
cin >> n >> m >> q;
Vec<i32> is_red(n, 0);
while (m--) {
i32 v;
cin >> v;
--v;
is_red[v] = 1;
}
Graph<WeightedEdge<i64>> g(n);
REP(i, n - 1) {
i32 u, v;
i64 w;
cin >> u >> v >> w;
--u;
--v;
g.add_undirected_edge(u, v, w);
}
HeavyLightDecomposition hld(g);
Vec<i64> dep(n, 0);
{
const auto dfs = [&](const auto &dfs, i32 v, i32 p) -> void {
for (const auto &e : g[v]) {
if (e.to != p) {
dep[e.to] = dep[v] + e.wt;
dfs(dfs, e.to, v);
}
}
};
dfs(dfs, 0, -1);
}
Vec<i64> nearest(n, 0);
{
const auto dfs = [&](const auto &dfs, i32 v, i32 p) -> void {
for (const auto &e : g[v]) {
if (e.to != p) {
if (!is_red[e.to]) {
nearest[e.to] = nearest[v] + e.wt;
}
dfs(dfs, e.to, v);
}
}
};
dfs(dfs, 0, -1);
}
DBG(nearest);
// original index, new parent
const auto sugoi = [&](Vec<i32> vs) -> pair<Vec<i32>, Vec<i32>> {
sort(ALL(vs), [&](i32 i, i32 j) -> bool {
return hld.in_time(i) < hld.in_time(j);
});
Vec<i32> stc;
stc.push_back(vs[0]);
Vec<i32> nvs = vs;
Vec<pair<i32, i32>> edges;
i32 sz = (i32)vs.size();
REP(i, sz - 1) {
i32 w = hld.lca(vs[i], vs[i + 1]);
if (w != vs[i]) {
i32 last = stc.back();
stc.pop_back();
while (!stc.empty() && hld.depth(w) < hld.depth(stc.back())) {
edges.emplace_back(last, stc.back());
last = stc.back();
stc.pop_back();
}
if (stc.empty() || stc.back() != w) {
stc.push_back(w);
nvs.push_back(w);
edges.emplace_back(last, w);
} else {
edges.emplace_back(last, w);
}
}
stc.push_back(vs[i + 1]);
}
REP(i, stc.size() - 1) {
edges.emplace_back(stc[i + 1], stc[i]);
}
sort(ALL(nvs));
nvs.erase(unique(ALL(nvs)), nvs.end());
Vec<i32> p(nvs.size(), -1);
for (auto [u, v] : edges) {
i32 u_ = (i32)(lower_bound(ALL(nvs), u) - nvs.begin());
i32 v_ = (i32)(lower_bound(ALL(nvs), v) - nvs.begin());
p[u_] = v_;
}
return make_pair(nvs, p);
};
const auto solve = [&](Vec<i32> vs) -> i64 {
i32 max_v = -1;
{
i64 mx = -INF64;
for (i32 v : vs) {
if (chmax(mx, nearest[v])) {
max_v = v;
}
}
}
vs.push_back(0);
Vec<i32> nvs, par;
tie(nvs, par) = sugoi(vs);
Vec<Vec<i32>> chl(nvs.size());
REP(i, 1, nvs.size()) {
chl[par[i]].push_back(i);
}
Vec<i32> imp(nvs.size(), 0);
for (i32 v : vs) {
i32 idx = (i32)(lower_bound(ALL(nvs), v) - nvs.begin());
imp[idx] = 1;
}
max_v = (i32)(lower_bound(ALL(nvs), max_v) - nvs.begin());
Vec<pair<i64, i64>> dp(nvs.size(), make_pair(-INF64, -INF64));
{
const auto dfs = [&](const auto &dfs, i32 v, i32 p) -> void {
for (i32 u : chl[v]) {
dfs(dfs, u, v);
chmax(dp[v].first, dp[u].first);
chmax(dp[v].second, dp[u].second);
}
if (imp[v]) {
chmax(dp[v].second, 0LL);
}{
if (p == -1 || nearest[nvs[v]] < dep[nvs[v]] - dep[nvs[p]]) {
chmax(dp[v].first, dp[v].second + nearest[nvs[v]]);
dp[v].second = -INF64;
} else {
dp[v].second += dep[nvs[v]] - dep[nvs[p]];
}
}
};
dfs(dfs, 0, -1);
}
DBG(nvs);
DBG(par);
DBG(dp);
Vec<i32> imp_ch(nvs.size(), -1);
DBG(max_v);
{
i32 cur = max_v;
while (cur > 0) {
imp_ch[par[cur]] = cur;
cur = par[cur];
}
}
DBG(imp);
DBG(imp_ch);
i64 ans = INF64;
i32 cur = 0;
i64 mx = 0; // 既に確定した部分
while (true) {
// cur を red にするときの答えを出す
DBG(cur); DBG(mx);
i64 this_ans = mx;
for (i32 c : chl[cur]) {
chmax(this_ans, dp[c].first);
chmax(this_ans, dp[c].second);
}
chmin(ans, this_ans);
for (i32 c : chl[cur]) {
if (c != imp_ch[cur]) {
chmax(mx, dp[c].first);
chmax(mx, dp[c].second + nearest[nvs[cur]]);
}
}
if (imp[cur]) {
chmax(mx, nearest[nvs[cur]]);
}
if (cur == max_v) {
break;
} else {
cur = imp_ch[cur];
}
}
return ans;
// 何回赤くしたか、まだ残っている最大値は何か
/*const auto dp = [&](const auto &dp, i32 v, i64 th, i32 p) -> pair<i32, i64> {
i32 cnt = 0;
i64 mx = -INF64;
for (i32 u : chl[v]) {
auto [a, b] = dp(dp, u, th, v);
cnt += a;
b += dep[nvs[u]] - dep[nvs[v]];
chmax(mx, b);
}
if (imp[v]) {
chmax(mx, 0LL);
}
if (is_red[nvs[v]]) {
mx = -INF64;
}
if (p != -1 && mx + min(dep[nvs[v]] - dep[nvs[par[v]]], nearest[nvs[v]]) > th) {
++cnt;
mx = -INF64;
}
return make_pair(cnt, mx);
};
i64 ok = 1e15, ng = -1;
while (ok - ng > 1) {
i64 mid = (ok + ng) / 2;
if (dp(dp, 0, mid, -1).first <= 1) {
ok = mid;
} else {
ng = mid;
}
}
return ok;*/
};
while (q--) {
i32 k;
cin >> k;
Vec<i32> v(k);
REP(i, k) {
cin >> v[i];
--v[i];
}
cout << solve(v) << '\n';
}
}
int main() {
i32 t;
cin >> t;
while (t--) {
solve();
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3720kb
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: 1251ms
memory: 24368kb
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