Submission #969625
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;
template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
ll ret = 1;
ll p = a % mod;
while (n) {
if (n & 1) ret = ret * p % mod;
p = p * p % mod;
n >>= 1;
}
return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
class CentroidDecomposition {
private:
using edge_t = Pii;
int g_to(const Pii& edge) { return edge.first; }
vector<vector<int>> e;
const int n;
vector<int> subtree_size; // buffer for compute_subtree_size
vector<int> depth, rank, parent;
int compute_subtree_size(int v, int par) {
int c = 1;
for (auto w : e[v]) {
if (w == par || rank[w] != -1) continue;
c += compute_subtree_size(w, v);
}
return subtree_size[v] = c;
}
Pii search_centroid(int v, int par, int sub_size) {
Pii ret(ten(9), -1);
int s = 1, m = 0;
for (auto w : e[v]) {
if (w == par || rank[w] != -1) continue;
ret = min(ret, search_centroid(w, v, sub_size));
m = max(m, subtree_size[w]);
s += subtree_size[w];
}
m = max(m, sub_size - s);
ret = min(ret, Pii(m, v));
return ret;
}
int build_centroid_decomposition_tree(int v, int par, int rnk, vector<vector<int>>& childs) {
compute_subtree_size(v, -1);
int s = search_centroid(v, -1, subtree_size[v]).second;
parent[s] = par;
rank[s] = rnk;
if (par != -1) childs[par].push_back(s);
for (auto w : e[s]) {
if (rank[w] != -1) continue;
build_centroid_decomposition_tree(w, s, rnk + 1, childs);
}
return s;
}
public:
template<int ARRAY_BUF>
CentroidDecomposition(vector<edge_t>(&e)[ARRAY_BUF], int n) :
n(n),
e(n),
subtree_size(n),
depth(n), rank(n, -1), parent(n) {
FOR(i, n) {
for (const edge_t& ed : e[i]) {
this->e[i].push_back(g_to(ed));
}
}
}
CentroidDecomposition(vector<vector<edge_t>>& e) :
n(sz(e)),
e(n),
subtree_size(n),
depth(n), rank(n, -1), parent(n) {
FOR(i, n) {
this->e[i].resize(sz(e[i]));
for (const edge_t& ed : e[i]) {
this->e[i].push_back(g_to(ed));
}
}
}
// pair<centroid_decomposition_tree, root_vertex>
// centroid_decomposition_tree = vector<vector<int>> directed graph
pair<vector<vector<int>>,int> build() {
vector<vector<int>> childs(n);
int root = build_centroid_decomposition_tree(0, -1, 0, childs);
return make_pair(childs, root);
}
};
Pll add(Pll& l, Pll& r) { return Pll(l.first + r.first, l.second + r.second); }
Pll sub(Pll& l, Pll& r) { return Pll(l.first - r.first, l.second - r.second); }
int min_cost[ten(5)];
vector<Pii> e[ten(5)];
bool centroid_used[ten(5)];
void enm(int v, int p, int len, vector <int>& ret, int cc_len) {
if (len > cc_len) return;
ret.push_back(len);
for (auto& kv : e[v]) {
if (centroid_used[kv.first]) continue;
if (kv.first == p) continue;
enm(kv.first, v, len + kv.second, ret, cc_len);
}
}
Pll cnt(vector<int>& ds, int len) {
static ll sm[ten(5) + 1];
sort(ds.begin(), ds.end());
sm[0] = 0;
FOR(i, sz(ds)) sm[i + 1] = sm[i] + ds[i];
int j = sz(ds);
Pll ret(0, 0);
FOR(i, sz(ds)) {
while (j > 0 && ds[i] + ds[j - 1] > len) j--;
ret.first += j;
ret.second += sm[j] + ll(ds[i]) * j;
if (j > i) {
// de-dup
ret.first--;
ret.second -= ds[i] * 2;
}
}
return Pll(ret.first / 2, ret.second / 2);
}
// 頂点sを重心とする部分木Sについての計算
// u-v-path (****uとvのpathに必ずsが含まれる****) ものについて、全て計算する
// e.x) u-v-pathの中で、距離がcc_len以下のpathを数え上げる, cc_len以下のpathのsumを計算する
Pll solve_dfs(int s, int cc_len, vector<vector<int>>& centroid_childs) {
centroid_used[s] = true; // 部分木を区切るのに使用
// phase 1
// 部分木に再帰的に適用する
Pll ret(0, 0);
for (auto& ch : centroid_childs[s]) {
if (centroid_used[ch]) continue;
//再帰的に小さい部分木に適用
Pll atmp = solve_dfs(ch, cc_len, centroid_childs);
ret = add(ret, atmp);
}
// phase 2
//頂点sからの距離を保存
vector<int> ds;
ds.push_back(0);
for (auto& kv : e[s]) {
if (centroid_used[kv.first]) continue;
// phase 2.1
// sと隣接する頂点が属する部分木について、sからの距離を計算
vector<int> tmp;
enm(kv.first, -1, kv.second, tmp, cc_len);
//phase 2.2
// phase 3で無駄に計算されるものを、あらかじめ引き算する。
Pll atmp = cnt(tmp, cc_len);
ret = sub(ret, atmp);
// phase 2.3
// sからの距離に追加
for (auto& x : tmp) ds.push_back(x);
}
// phase 3
// この部分木についての計算をする
// dsには、sからの距離が入っているので、u-v-pathの距離がcc_len以下となるような(u,v)の個数が計算出来る
// ただしここで計算した結果には u-v-pathに****sが含まれない****ものも含まれているので、
// phase2.3で事前に引き算をしておく
Pll btmp = cnt(ds, cc_len);
ret = add(ret, btmp);
centroid_used[s] = false;
return ret;
}
ll solve(int n, int x) {
CentroidDecomposition cd(e, n);
vector<vector<int>> centroid_childs;
int root;
tie(centroid_childs,root) = cd.build();
Pll cnt = solve_dfs(root, x, centroid_childs);
ll origin_path_count = cnt.first;
ll sum = cnt.second;
FOR(i, n) {
min_cost[i] = ten(9);
for (auto& kv : e[i]) min_cost[i] = min(min_cost[i], kv.second);
}
FOR(u, n) {
for (auto& kv : e[u]) {
int t, c; tie(t, c) = kv;
if (u > t) continue;
if (c <= x) continue; // already counted
int cost = c;
if (sz(e[u]) != n - 1) {
cost = min(cost, x + min_cost[t]);
}
if (sz(e[t]) != n - 1) {
cost = min(cost, x + min_cost[u]);
}
if (sz(e[u]) + sz(e[t]) != n) {
cost = min(cost, x + x);
}
if (sz(e[u]) != 1 && sz(e[t]) != 1) {
cost = min(cost, x + x + x);
}
origin_path_count++;
sum += cost;
}
}
ll black = ll(n) * (n - 1) / 2 - origin_path_count;
sum += black * x;
return sum;
}
int main() {
int n, x; reader(n, x);
FOR(i, n - 1) {
int u, v, c; reader(u, v, c);
u--; v--;
e[u].emplace_back(v, c);
e[v].emplace_back(u, c);
}
ll ans = 0;
ll c = solve(n, x);
writerLn(c);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 道路網 |
User |
math |
Language |
C++14 (GCC 5.4.1) |
Score |
1200 |
Code Size |
9508 Byte |
Status |
AC |
Exec Time |
330 ms |
Memory |
28800 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 |
5 ms |
2560 KB |
00_example_02.txt |
AC |
5 ms |
2560 KB |
10_rand_01.txt |
AC |
5 ms |
2560 KB |
10_rand_02.txt |
AC |
5 ms |
2688 KB |
10_rand_03.txt |
AC |
5 ms |
2688 KB |
10_rand_04.txt |
AC |
5 ms |
2688 KB |
10_rand_05.txt |
AC |
5 ms |
2688 KB |
20_k-ary_01.txt |
AC |
279 ms |
21376 KB |
20_k-ary_02.txt |
AC |
276 ms |
21376 KB |
20_k-ary_03.txt |
AC |
281 ms |
21376 KB |
20_k-ary_04.txt |
AC |
180 ms |
20608 KB |
20_k-ary_05.txt |
AC |
140 ms |
20608 KB |
20_k-ary_06.txt |
AC |
94 ms |
19840 KB |
20_k-ary_07.txt |
AC |
87 ms |
20480 KB |
20_k-ary_08.txt |
AC |
85 ms |
19840 KB |
20_k-ary_09.txt |
AC |
84 ms |
19456 KB |
20_k-ary_10.txt |
AC |
85 ms |
19456 KB |
30_star_01.txt |
AC |
63 ms |
19572 KB |
30_star_02.txt |
AC |
63 ms |
19572 KB |
30_star_03.txt |
AC |
66 ms |
19572 KB |
30_star_04.txt |
AC |
69 ms |
19572 KB |
30_star_05.txt |
AC |
71 ms |
19572 KB |
40_pseudostar_01.txt |
AC |
79 ms |
19572 KB |
40_pseudostar_02.txt |
AC |
68 ms |
19572 KB |
40_pseudostar_04.txt |
AC |
74 ms |
19576 KB |
40_pseudostar_05.txt |
AC |
72 ms |
19828 KB |
40_pseudostar_06.txt |
AC |
71 ms |
19448 KB |
50_line_01.txt |
AC |
308 ms |
28800 KB |
50_line_02.txt |
AC |
296 ms |
28800 KB |
50_line_03.txt |
AC |
302 ms |
28800 KB |
60_max_01.txt |
AC |
258 ms |
20864 KB |
60_max_02.txt |
AC |
259 ms |
20864 KB |
60_max_03.txt |
AC |
218 ms |
20864 KB |
60_max_04.txt |
AC |
239 ms |
20864 KB |
70_hand_01.txt |
AC |
5 ms |
2560 KB |
70_hand_02.txt |
AC |
5 ms |
2560 KB |
71_hand_01.txt |
AC |
167 ms |
20864 KB |
72_hand_01.txt |
AC |
330 ms |
28800 KB |
80_kill2X_01.txt |
AC |
63 ms |
19572 KB |
80_kill2X_02.txt |
AC |
64 ms |
19444 KB |
80_kill2X_03.txt |
AC |
71 ms |
19572 KB |
80_kill2X_04.txt |
AC |
63 ms |
19572 KB |
80_kill2X_05.txt |
AC |
64 ms |
19828 KB |
80_kill2X_06.txt |
AC |
63 ms |
19448 KB |
80_kill2X_07.txt |
AC |
64 ms |
19448 KB |
80_kill2X_08.txt |
AC |
64 ms |
19448 KB |