結果

問題 No.1212 Second Path
ユーザー risujiroh
提出日時 2020-08-30 15:01:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 312 ms / 3,000 ms
コード長 7,868 bytes
コンパイル時間 5,253 ms
コンパイル使用メモリ 275,284 KB
最終ジャッジ日時 2025-01-13 22:24:15
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/extc++.h>
#ifndef DUMP
#define DUMP(...) void(0)
#endif
using namespace std;
struct graph {
struct edge {
int src, dst;
int64_t cost;
int operator-(int v) const { return src ^ dst ^ v; }
};
int n, m;
vector<edge> edges;
vector<vector<pair<int, int>>> adj;
graph(int _n = 0) : n(_n), m(0), adj(n) {}
int add(const edge& e, bool directed = false) {
edges.push_back(e);
adj[e.src].emplace_back(m, e.dst);
if (not directed) adj[e.dst].emplace_back(m, e.src);
return m++;
}
};
struct dfs_forest : graph {
using T = decltype(edge::cost);
vector<int> root, pv, pe, sz, dep, min_dep, last, ord, in, out;
vector<T> dist;
int trials;
dfs_forest(int _n = 0) : graph(_n), dist(n), trials(0) {
for (auto p : {&root, &pv, &pe, &sz, &dep, &min_dep, &last, &in, &out})
p->assign(n, -1);
}
int add(const edge& e) { return graph::add(e); }
void dfs(int v) {
sz[v] = 1, min_dep[v] = dep[v], last[v] = trials;
in[v] = size(ord), ord.push_back(v);
for (auto [id, u] : adj[v]) {
if (id == pe[v]) continue;
if (last[u] == trials) {
min_dep[v] = min(min_dep[v], dep[u]);
continue;
}
root[u] = root[v], pv[u] = v, pe[u] = id, dep[u] = dep[v] + 1;
dist[u] = dist[v] + edges[id].cost;
dfs(u);
sz[v] += sz[u], min_dep[v] = min(min_dep[v], min_dep[u]);
}
out[v] = size(ord);
}
void build(int r, bool clear_ord = true) {
root[r] = r, pv[r] = pe[r] = -1, dep[r] = 0, dist[r] = T{};
if (clear_ord) ord.clear();
dfs(r);
++trials;
}
void build() {
fill(begin(root), end(root), -1);
for (int v = 0; v < n; ++v)
if (root[v] == -1) build(v, v == 0);
}
int farther(int id) const {
int u = edges[id].src, v = edges[id].dst;
return dep[u] < dep[v] ? v : u;
}
bool spans(int id) const { return id == pe[farther(id)]; }
bool anc(int u, int v) const { return in[u] <= in[v] and out[v] <= out[u]; }
};
struct hld_forest : dfs_forest {
vector<int> head;
hld_forest(int _n = 0) : dfs_forest(_n), head(n) {}
void dfs_hld(int v) {
in[v] = size(ord), ord.push_back(v);
sort(begin(adj[v]), end(adj[v]), [&](auto a, auto b) {
int au = a.second, bu = b.second;
return (a.first == pe[au]) * sz[au] > (b.first == pe[bu]) * sz[bu];
});
for (auto [id, u] : adj[v]) {
if (id == pe[v] or not spans(id)) continue;
head[u] = u == adj[v][0].second ? head[v] : u;
dfs_hld(u);
}
out[v] = size(ord);
}
void build_hld(int r, bool clear_ord = true) {
build(r, clear_ord);
ord.erase(end(ord) - sz[r], end(ord));
head[r] = r;
dfs_hld(r);
}
void build_hld() {
fill(begin(root), end(root), -1);
for (int v = 0; v < n; ++v)
if (root[v] == -1) build_hld(v, v == 0);
}
int lca(int u, int v) const {
assert(root[u] == root[v]);
while (true) {
if (in[u] > in[v]) swap(u, v);
if (head[u] == head[v]) return u;
v = pv[head[v]];
}
}
int d(int u, int v) const { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
T distance(int u, int v) const {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
int la(int v, int d) const {
assert(0 <= d), assert(d <= dep[v]);
while (dep[head[v]] > d) v = pv[head[v]];
return ord[in[head[v]] + (d - dep[head[v]])];
}
int next(int src, int dst) const {
assert(root[src] == root[dst]), assert(src != dst);
if (not anc(src, dst)) return pv[src];
return la(dst, dep[src] + 1);
}
int next(int src, int dst, int k) const {
assert(root[src] == root[dst]), assert(k >= 0);
int v = lca(src, dst);
if (k <= dep[src] - dep[v]) return la(src, dep[src] - k);
k -= dep[src] - dep[v];
assert(k <= dep[dst] - dep[v]);
return la(dst, dep[v] + k);
}
vector<pair<int, int>> ascend(int src, int dst) const {
vector<pair<int, int>> res;
while (head[src] != head[dst]) {
res.emplace_back(in[src], in[head[src]]);
src = pv[head[src]];
}
if (src != dst) res.emplace_back(in[src], in[dst] + 1);
return res;
}
vector<pair<int, int>> descend(int src, int dst) const {
if (src == dst) return {};
if (head[src] == head[dst]) return {{in[src] + 1, in[dst]}};
auto res = descend(src, pv[head[dst]]);
res.emplace_back(in[head[dst]], in[dst]);
return res;
}
template <class F>
void run(int src, int dst, F f, bool vertex = true) const {
assert(root[src] == root[dst]);
int v = lca(src, dst);
for (auto [a, b] : ascend(src, v)) f(a + 1, b);
if (vertex) f(in[v], in[v] + 1);
for (auto [a, b] : descend(v, dst)) f(a, b + 1);
}
};
constexpr int inf = 0x3f3f3f3f;
template <class T>
struct segtree {
int n;
vector<T> t;
segtree(int _n = 0) : n(_n), t(2 * n) {}
T& operator[](int i) { return t[n + i]; }
void build() {
for (int i = n; i-- > 1;) t[i] = t[2 * i] * t[2 * i + 1];
}
T fold(int l, int r) const {
T a{}, b{};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) a = a * t[l++];
if (r & 1) b = t[--r] * b;
}
return a * b;
}
void set(int i, const T& a) {
t[i += n] = a;
while (i >>= 1) t[i] = t[2 * i] * t[2 * i + 1];
}
};
struct node {
int v;
node(int _v = inf) : v(_v) {}
operator int() const { return v; }
friend node operator*(const node& a, const node& b) {
return b.v < a.v ? b : a;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
hld_forest g(n);
for (int _ = n - 1; _--;) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g.add({u, v, w});
}
g.build_hld();
segtree<node> seg(n);
vector<segtree<node>> ch(n);
vector<int> sz(n);
for (int v = 0; v < n; ++v) {
sz[v] = size(g.adj[v]) - (v >= 1);
ch[v] = sz[v];
for (int i = 0; i < sz[v]; ++i) {
auto [id, u] = g.adj[v][i];
ch[v][i] = g.edges[id].cost;
}
ch[v].build();
for (int i = 0; i < sz[v]; ++i) {
auto [id, u] = g.adj[v][i];
seg[g.in[u]] = min(ch[v].fold(0, i), ch[v].fold(i + 1, sz[v]));
}
}
seg.build();
auto fold = [&](int u, int v) {
int res = inf;
g.run(
u, v,
[&](int l, int r) {
if (l > r) swap(l, r);
res = min<int>(res, seg.fold(l, r));
},
false);
return res;
};
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
--u, --v;
if (g.in[u] > g.in[v]) swap(u, v);
int a = g.lca(u, v);
int64_t res = g.distance(u, v);
int mn = inf;
if (u == a) {
mn = min(mn, fold(u, v));
mn = min<int>(mn, ch[v].fold(0, sz[v]));
} else {
int au = g.next(a, u);
int av = g.next(a, v);
mn = min(mn, fold(u, au));
mn = min(mn, fold(v, av));
mn = min<int>(mn, ch[u].fold(0, sz[u]));
mn = min<int>(mn, ch[v].fold(0, sz[v]));
assert(g.in[au] < g.in[av]);
int x = partition_point(
begin(g.adj[a]), begin(g.adj[a]) + sz[a],
[&](auto idu) { return g.in[idu.second] < g.in[au]; }) -
begin(g.adj[a]);
int y = partition_point(
begin(g.adj[a]), begin(g.adj[a]) + sz[a],
[&](auto idu) { return g.in[idu.second] < g.in[av]; }) -
begin(g.adj[a]);
mn = min<int>(mn, ch[a].fold(0, x));
mn = min<int>(mn, ch[a].fold(x + 1, y));
mn = min<int>(mn, ch[a].fold(y + 1, sz[a]));
}
if (a) mn = min<int>(mn, g.edges[g.pe[a]].cost);
if (mn == inf)
res = -1;
else
res += 2 * mn;
cout << res << '\n';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0