#544068 (C++17) No.1212 Second Path

提出ソース

結果

問題	No.1212 Second Path
ユーザー	risujiroh
提出日時	2020-08-30 14:57:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	7,596 bytes
コンパイル時間	5,472 ms
コンパイル使用メモリ	289,588 KB
実行使用メモリ	816,440 KB
最終ジャッジ日時	2024-11-15 08:15:28
合計ジャッジ時間	60,434 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	MLE	-
testcase_01	MLE	-
testcase_02	MLE	-
testcase_03	MLE	-
testcase_04	MLE	-
testcase_05	MLE	-
testcase_06	MLE	-
testcase_07	MLE	-
testcase_08	MLE	-
testcase_09	MLE	-
testcase_10	MLE	-
testcase_11	MLE	-
testcase_12	MLE	-
testcase_13	MLE	-
testcase_14	MLE	-
testcase_15	MLE	-
testcase_16	MLE	-
testcase_17	MLE	-
testcase_18	AC	47 ms 6,692 KB
testcase_19	AC	43 ms 6,688 KB
testcase_20	AC	42 ms 6,688 KB
testcase_21	AC	39 ms 6,816 KB
testcase_22	AC	51 ms 6,820 KB
testcase_23	AC	25 ms 6,820 KB
testcase_24	AC	30 ms 6,820 KB
testcase_25	AC	27 ms 6,820 KB
testcase_26	AC	35 ms 6,820 KB
testcase_27	AC	28 ms 6,816 KB
testcase_28	AC	28 ms 6,816 KB
testcase_29	MLE	-
testcase_30	MLE	-
testcase_31	MLE	-
testcase_32	MLE	-
testcase_33	MLE	-
testcase_34	MLE	-
testcase_35	MLE	-
testcase_36	MLE	-
testcase_37	MLE	-
testcase_38	MLE	-
testcase_39	MLE	-
testcase_40	AC	74 ms 14,976 KB
testcase_41	MLE	-
testcase_42	AC	5 ms 6,688 KB
testcase_43	AC	3 ms 6,688 KB
testcase_44	AC	3 ms 6,688 KB
testcase_45	MLE	-
testcase_46	MLE	-
testcase_47	MLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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';
  }
}

yukicoder

結果

テストケース

ソースコード