| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1130679 | CrabCNH | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define task "brianthecrab"
#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define szf sizeof
#define sz(s) (int)((s).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}
const int N = 1e6 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;
int n, k;
int tt;
struct CD {
int sz[N], edgecnt[N], exist[N];
set <pii> G[N];
// get sz
int dfs (int u, int p) {
sz[u] = 1;
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
sz[u] += dfs (v, u);
}
return sz[u];
}
// find centroid
int centroid (int u, int p, int nn) {
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
if (sz[v] > nn / 2) {
return centroid (v, u, nn);
}
}
return u;
}
// exist kiem tra xem da co gia tri want o trong cac cay con goc centroid da xet chua
// neu co cap nhat lai ans
// neu ma gia tri d van nho hon k thi ta se push no vao 1 vector
// khi do xet tiep cac dinh ke canh hien tai va roi xet tiep den cay goc tiep theo
// cap nhat lai gia tri ans khi xet duoc con tot nhat o 1 cay con nao day
int dfs2 (int u, int p, int d, int cnt, int t, vector <pii> &vv) {
int want = k - d;
int ans = inf;
if (want >= 0 && exist[want] == t) {
mini (ans, cnt + edgecnt[want]);
}
if (d <= k) {
vv.push_back ({d, cnt});
for (auto [v, dis] : G[u]) {
if (v == p) {
continue;
}
int cur = dfs2 (v, u, d + dis, cnt + 1, t, vv);
mini (ans, cur);
}
}
return ans;
}
/*
Solve(u):
ans = inf
for v là con u:
ans = min(ans, Solve(v))
DFS từ u để tính khoảng cách và số cạnh đã sử dụng trong thành phần của u
Sử dụng DFS khác để tính kết quả, trong khi sử dụng một mảnh để truy vết các đường đi thỏa mãn bắt đầu từ
u và số cạnh cần dùng ít nhất
cập nhật ans từ hàm DFS trước
return ans
*/
int sol (int u, int p) {
int nn = dfs (u, p);
int c = centroid (u, p, nn);
int ans = inf;
int t = ++tt;
exist[0] = t;
edgecnt[0] = 0;
for (auto [v, dis] : G[c]) {
vector <pii> tmp;
int cur = dfs2 (v, c, dis, 1, t, tmp);
mini (ans, cur);
for (auto [v1, dis1] : tmp) {
if (exist[v1] != t || (exist[v1] == t && edgecnt[v1] > dis1)) {
exist[v1] = t;
edgecnt[v1] = dis1;
}
}
}
vector <pii> tmp (G[c].begin (), G[c].end ());
for (auto [v, dis] : tmp) {
G[c].erase ({v, dis});
G[v].erase ({c, dis});
int cur = sol (v, c);
mini (ans, cur);
}
return ans;
}
} T;
signed main () {
ios_base :: sync_with_stdio (0);
cin.tie (0);
cout.tie (0);
if (fopen (task".inp", "r")) {
freopen (task".inp", "r", stdin);
freopen (task".out", "w", stdout);
}
cin >> n >> k;
for (int i = 1; i <= n - 1; i ++) {
int u, v, w;
cin >> u >> v >> w;
T.G[u].insert ({v, w});
T.G[v].insert ({u, w});
}
tt = 0;
int ans = T.sol (0, -1);
cout << (ans == inf ? - 1 : ans);
return 0;
}
// hmvncvdqdela