結果

問題 No.1212 Second Path
ユーザー risujirohrisujiroh
提出日時 2020-08-30 14:57:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 7,596 bytes
コンパイル時間 4,455 ms
コンパイル使用メモリ 291,036 KB
実行使用メモリ 814,640 KB
最終ジャッジ日時 2024-04-27 07:51:09
合計ジャッジ時間 9,980 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
権限があれば一括ダウンロードができます

ソースコード

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 sparse_table {
  vector<vector<T>> t;
  sparse_table(const vector<T>& v = {}) : t{v} {
    for (int k = 1, n = size(v); 1 << k <= n; ++k) {
      t.emplace_back(n - (1 << k) + 1);
      for (int i = 0; i + (1 << k) <= n; ++i)
        t[k][i] = min(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
    }
  }
  T fold(int l, int r) const {
    assert(l <= r);
    if (l == r) return inf;
    int k = __lg(r - l);
    return min(t[k][l], t[k][r - (1 << k)]);
  }
};

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();

  vector _st(n, inf);
  vector<sparse_table<int>> ch(n);
  vector<int> sz(n);
  for (int v = 0; v < n; ++v) {
    sz[v] = size(g.adj[v]) - (v >= 1);
    vector<int> chv(sz);
    for (int i = 0; i < sz[v]; ++i) {
      auto [id, u] = g.adj[v][i];
      chv[i] = g.edges[id].cost;
    }
    ch[v] = chv;
    for (int i = 0; i < sz[v]; ++i) {
      auto [id, u] = g.adj[v][i];
      _st[g.in[u]] = min(ch[v].fold(0, i), ch[v].fold(i + 1, sz[v]));
    }
  }
  sparse_table st(_st);

  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(res, st.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(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(mn, ch[u].fold(0, sz[u]));
      mn = min(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(mn, ch[a].fold(0, x));
      mn = min(mn, ch[a].fold(x + 1, y));
      mn = min(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';
  }
}
0