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 |
|
|
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 |