Submission #968836
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>;
int min_cost[ten(5)];
vector<Pii> e[ten(5)];
const int MAX_SIZE = ten(5);
int centroid_subtree_size[MAX_SIZE];
int centroid_depth[MAX_SIZE], centroid_rank[MAX_SIZE], centroid_parent[MAX_SIZE];
struct P {
ll sum, parent_sum, count;
};
P centroid_data[MAX_SIZE];
//depthの設定
void centroid_dfs(int v, int par, int depth) {
centroid_depth[v] = depth;
for (auto p : e[v]) {
if (p.first == par) continue;
centroid_dfs(p.first, v, depth + 1);
}
}
int centroid_compute_subtree_size(int v, int par) {
int c = 1;
for (auto t : e[v]) {
int w = t.first;
if (w == par || centroid_rank[w] != -1) continue;
c += centroid_compute_subtree_size(w, v);
}
return centroid_subtree_size[v] = c;
}
Pii centroid_search_centroid(int v, int par, int sub_size) {
Pii ret(ten(9), -1);
int s = 1, m = 0;
for (auto t : e[v]) {
int w = t.first;
if (w == par || centroid_rank[w] != -1) continue;
ret = min(ret, centroid_search_centroid(w, v, sub_size));
m = max(m, centroid_subtree_size[w]);
s += centroid_subtree_size[w];
}
m = max(m, sub_size - s);
ret = min(ret, Pii(m, v));
return ret;
}
int centroid_sub(int v, int par, int rank) {
centroid_compute_subtree_size(v, -1);
int s = centroid_search_centroid(v, -1, centroid_subtree_size[v]).second;
centroid_parent[s] = par;
centroid_rank[s] = rank;
for (auto t : e[s]) {
if (centroid_rank[t.first] != -1) continue;
centroid_sub(t.first, s, rank + 1);
}
return s;
}
bool centroid_used[ten(5)];
void enm(int v, int p, int len, vector < int>& ret) {
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);
}
}
ll sm[ten(5) + 1];
Pll cnt(vector<int>& ds, int len) {
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);
}
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);
}
Pll solve_dfs(int s, int cc_len) {
centroid_compute_subtree_size(s, -1);
s = centroid_search_centroid(s, -1, centroid_subtree_size[s]).second;
centroid_used[s] = true;
Pll ret(0,0);
for (auto& kv : e[s]) {
if (centroid_used[kv.first]) continue;
Pll atmp = solve_dfs(kv.first, cc_len);
ret = add(ret, atmp);
}
vector<int> ds;
ds.push_back(0);
for (auto& kv : e[s]) {
if (centroid_used[kv.first]) continue;
vector<int> tmp;
enm(kv.first, -1, kv.second, tmp);
Pll atmp = cnt(tmp, cc_len);
ret = sub(ret, atmp);
for (auto& x : tmp) ds.push_back(x);
}
Pll btmp = cnt(ds, cc_len);
ret = add(ret, btmp);
centroid_used[s] = false;
return ret;
}
ll solve(int n, int x) {
memset(centroid_rank, -1, sizeof(centroid_rank));
memset(centroid_data, 0, sizeof(centroid_data));
int s = centroid_sub(0, -1, -0);
Pll cnt = solve_dfs(0, x);
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]) != n - 1 && sz(e[t]) != n - 1) {
cost = min(cost, 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 |
0 |
Code Size |
7669 Byte |
Status |
TLE |
Exec Time |
3155 ms |
Memory |
23688 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
8 ms |
5376 KB |
00_example_02.txt |
AC |
8 ms |
5376 KB |
10_rand_01.txt |
AC |
8 ms |
5376 KB |
10_rand_02.txt |
AC |
8 ms |
5376 KB |
10_rand_03.txt |
AC |
8 ms |
5376 KB |
10_rand_04.txt |
AC |
8 ms |
5376 KB |
10_rand_05.txt |
AC |
8 ms |
5376 KB |
20_k-ary_01.txt |
AC |
442 ms |
12248 KB |
20_k-ary_02.txt |
AC |
400 ms |
12248 KB |
20_k-ary_03.txt |
AC |
440 ms |
12248 KB |
20_k-ary_04.txt |
AC |
245 ms |
12584 KB |
20_k-ary_05.txt |
AC |
183 ms |
12804 KB |
20_k-ary_06.txt |
AC |
99 ms |
12412 KB |
20_k-ary_07.txt |
AC |
89 ms |
12720 KB |
20_k-ary_08.txt |
AC |
87 ms |
12404 KB |
20_k-ary_09.txt |
AC |
86 ms |
12272 KB |
20_k-ary_10.txt |
AC |
88 ms |
12272 KB |
30_star_01.txt |
AC |
68 ms |
12140 KB |
30_star_02.txt |
AC |
68 ms |
12140 KB |
30_star_03.txt |
AC |
71 ms |
12140 KB |
30_star_04.txt |
AC |
68 ms |
12140 KB |
30_star_05.txt |
AC |
68 ms |
12140 KB |
40_pseudostar_01.txt |
AC |
67 ms |
12148 KB |
40_pseudostar_02.txt |
AC |
73 ms |
12148 KB |
40_pseudostar_04.txt |
AC |
74 ms |
12260 KB |
40_pseudostar_05.txt |
AC |
74 ms |
12148 KB |
40_pseudostar_06.txt |
AC |
78 ms |
12148 KB |
50_line_01.txt |
TLE |
3155 ms |
23688 KB |
50_line_02.txt |
TLE |
3155 ms |
23688 KB |
50_line_03.txt |
TLE |
3155 ms |
23688 KB |
60_max_01.txt |
AC |
844 ms |
11984 KB |
60_max_02.txt |
AC |
585 ms |
11976 KB |
60_max_03.txt |
AC |
360 ms |
12056 KB |
60_max_04.txt |
AC |
585 ms |
12016 KB |
70_hand_01.txt |
AC |
8 ms |
5376 KB |
70_hand_02.txt |
AC |
8 ms |
5376 KB |
71_hand_01.txt |
AC |
746 ms |
12012 KB |
72_hand_01.txt |
TLE |
3155 ms |
23688 KB |
80_kill2X_01.txt |
AC |
67 ms |
12140 KB |
80_kill2X_02.txt |
AC |
68 ms |
12140 KB |
80_kill2X_03.txt |
AC |
70 ms |
12140 KB |
80_kill2X_04.txt |
AC |
75 ms |
12140 KB |
80_kill2X_05.txt |
AC |
68 ms |
12276 KB |
80_kill2X_06.txt |
AC |
66 ms |
12148 KB |
80_kill2X_07.txt |
AC |
69 ms |
12072 KB |
80_kill2X_08.txt |
AC |
69 ms |
12272 KB |