Submission #4624651


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const int64 infll = (1LL << 61) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename G >
struct CentroidDecomposition {
  const G &g;
  vector< int > sub;
  vector< vector< int > > belong;
  vector< bool > v;

  CentroidDecomposition(const G &g) : g(g), sub(g.size()), v(g.size()), belong(g.size()) {}

  inline int build_dfs(int idx, int par) {
    sub[idx] = 1;
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      sub[idx] += build_dfs(to, idx);
    }
    return sub[idx];
  }

  inline int search_centroid(int idx, int par, const int mid) {
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      if(sub[to] > mid) return search_centroid(to, idx, mid);
    }
    return idx;
  }

  inline void belong_dfs(int idx, int par, int centroid) {
    belong[idx].emplace_back(centroid);
    for(auto &to : g[idx]) {
      if(to == par || v[to]) continue;
      belong_dfs(to, idx, centroid);
    }
  }

  inline int build(UnWeightedGraph &t, int idx) {
    int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2);
    v[centroid] = true;
    belong_dfs(centroid, -1, centroid);
    for(auto &to : g[centroid]) {
      if(!v[to]) t[centroid].emplace_back(build(t, to));
    }
    v[centroid] = false;
    return centroid;
  }

  inline int build(UnWeightedGraph &t) {
    t.resize(g.size());
    return build(t, 0);
  }
};

template< class T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree() {}

  void init(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};

int main() {
  int N;
  int64 X;
  cin >> N >> X;
  WeightedGraph< int > g(N);
  for(int i = 0; i < N - 1; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }
  vector< pair< int, int > > top2[100000];
  for(int i = 0; i < N; i++) {
    sort(begin(g[i]), end(g[i]), [&](auto x, auto y) {
      return x.cost < y.cost;
    });
    for(int j = 0; j < 2; j++) {
      if(j < g[i].size()) top2[i].emplace_back(g[i][j].to, g[i][j].cost);
      else top2[i].emplace_back(-1, inf);
    }
  }

  int64 ans = 0;

  CentroidDecomposition< WeightedGraph< int > > cd(g);
  UnWeightedGraph t;
  vector< int > used(N);
  vector< int > cash(N);
  vector< int64 > xs;
  BinaryIndexedTree< int64 > bit1, bit2;
  function< void(int, int, int64) > add_path = [&](int idx, int par, int64 d) {
    xs.emplace_back(d);
    for(auto to : g[idx]) {
      if(used[to]) continue;
      if(to == par) continue;
      add_path(to, idx, d + to.cost);
    }
  };
  function< void(int, int, int64) > cash_path = [&](int idx, int par, int64 d) {
    cash[idx] = lower_bound(begin(xs), end(xs), d) - begin(xs);
    for(auto to : g[idx]) {
      if(used[to]) continue;
      if(to == par) continue;
      cash_path(to, idx, d + to.cost);
    }
  };
  function< void(int) > update = [&](int idx) {
    bit1.add(cash[idx], xs[cash[idx]]);
    bit2.add(cash[idx], 1);
  };
  function< void(int, int, int64, bool) > query_path = [&](int idx, int par, int64 d, bool direct) {
    int64 rest = X - d;
    int all = bit2.sum((int) xs.size() - 1);
    int pos = lower_bound(begin(xs), end(xs), rest) - begin(xs);
    int divall = bit2.sum(pos - 1);
    int64 add = 0;
    if(!direct) add += min(X, d);
    add += bit1.sum(pos - 1);
    add += d * divall;
    add += X * (all - divall);
    ans += add;
    for(auto to : g[idx]) {
      if(used[to]) continue;
      if(to == par) continue;
      query_path(to, idx, d + to.cost, false);
    }
  };
  function< void(int, int) > add_path2 = [&](int idx, int par) {
    update(idx);
    for(auto to : g[idx]) {
      if(used[to]) continue;
      if(to == par) continue;
      add_path2(to, idx);
    }
  };
  function< void(int) > dfs = [&](int idx) {
    used[idx] = true;
    xs.clear();
    add_path(idx, -1, 0);
    sort(begin(xs), end(xs));
    xs.erase(unique(begin(xs), end(xs)), end(xs));
    bit1.init(xs.size());
    bit2.init(xs.size());
    cash_path(idx, -1, 0);
    int pub = ans;
    for(auto to : g[idx]) {
      if(used[to]) continue;
      query_path(to, idx, to.cost, true);
      add_path2(to, idx);
    }
    for(auto to : g[idx]) {
      if(used[to]) continue;
      int64 cost = min((int64) to.cost, min(top2[idx][top2[idx][0].first == to].second, top2[to][top2[to][0].first == idx].second) + X);
      if(g[idx].size() + g[to].size() != N) chmin(cost, 2 * X);
      ans += cost;
    };
    for(auto to : t[idx]) dfs(to);
  };
  dfs(cd.build(t));
  cout << ans << endl;
}

Submission Info

Submission Time
Task D - 道路網
User ei13333
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 6789 Byte
Status AC
Exec Time 678 ms
Memory 36340 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 2
AC × 46
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt
All 00_example_01.txt, 00_example_02.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 20_k-ary_01.txt, 20_k-ary_02.txt, 20_k-ary_03.txt, 20_k-ary_04.txt, 20_k-ary_05.txt, 20_k-ary_06.txt, 20_k-ary_07.txt, 20_k-ary_08.txt, 20_k-ary_09.txt, 20_k-ary_10.txt, 30_star_01.txt, 30_star_02.txt, 30_star_03.txt, 30_star_04.txt, 30_star_05.txt, 40_pseudostar_01.txt, 40_pseudostar_02.txt, 40_pseudostar_04.txt, 40_pseudostar_05.txt, 40_pseudostar_06.txt, 50_line_01.txt, 50_line_02.txt, 50_line_03.txt, 60_max_01.txt, 60_max_02.txt, 60_max_03.txt, 60_max_04.txt, 70_hand_01.txt, 70_hand_02.txt, 71_hand_01.txt, 72_hand_01.txt, 80_kill2X_01.txt, 80_kill2X_02.txt, 80_kill2X_03.txt, 80_kill2X_04.txt, 80_kill2X_05.txt, 80_kill2X_06.txt, 80_kill2X_07.txt, 80_kill2X_08.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 3 ms 2560 KB
00_example_02.txt AC 3 ms 2560 KB
10_rand_01.txt AC 3 ms 2688 KB
10_rand_02.txt AC 3 ms 2688 KB
10_rand_03.txt AC 3 ms 2688 KB
10_rand_04.txt AC 4 ms 2688 KB
10_rand_05.txt AC 4 ms 2688 KB
20_k-ary_01.txt AC 603 ms 29196 KB
20_k-ary_02.txt AC 585 ms 29196 KB
20_k-ary_03.txt AC 543 ms 29196 KB
20_k-ary_04.txt AC 356 ms 28024 KB
20_k-ary_05.txt AC 242 ms 25720 KB
20_k-ary_06.txt AC 155 ms 23420 KB
20_k-ary_07.txt AC 141 ms 24060 KB
20_k-ary_08.txt AC 134 ms 23424 KB
20_k-ary_09.txt AC 139 ms 23040 KB
20_k-ary_10.txt AC 138 ms 22912 KB
30_star_01.txt AC 126 ms 23604 KB
30_star_02.txt AC 128 ms 23604 KB
30_star_03.txt AC 127 ms 23604 KB
30_star_04.txt AC 128 ms 23604 KB
30_star_05.txt AC 121 ms 23604 KB
40_pseudostar_01.txt AC 138 ms 23732 KB
40_pseudostar_02.txt AC 155 ms 24116 KB
40_pseudostar_04.txt AC 142 ms 23860 KB
40_pseudostar_05.txt AC 147 ms 24244 KB
40_pseudostar_06.txt AC 144 ms 24244 KB
50_line_01.txt AC 627 ms 36340 KB
50_line_02.txt AC 678 ms 36340 KB
50_line_03.txt AC 670 ms 36340 KB
60_max_01.txt AC 580 ms 28660 KB
60_max_02.txt AC 562 ms 28544 KB
60_max_03.txt AC 469 ms 27652 KB
60_max_04.txt AC 528 ms 28148 KB
70_hand_01.txt AC 2 ms 2560 KB
70_hand_02.txt AC 3 ms 2560 KB
71_hand_01.txt AC 431 ms 28288 KB
72_hand_01.txt AC 571 ms 35444 KB
80_kill2X_01.txt AC 129 ms 23604 KB
80_kill2X_02.txt AC 131 ms 23604 KB
80_kill2X_03.txt AC 140 ms 23604 KB
80_kill2X_04.txt AC 133 ms 23604 KB
80_kill2X_05.txt AC 126 ms 23732 KB
80_kill2X_06.txt AC 119 ms 23352 KB
80_kill2X_07.txt AC 144 ms 23352 KB
80_kill2X_08.txt AC 127 ms 23352 KB