| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162471 | CrabCNH | Race (IOI11_race) | C++20 | 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 inf = 1e18 + 7;
const int mod = 1e9 + 7;
int n, k;
int tt;
struct CD {
int sz[1000005], edgecnt[1000005], exist[1000005];
set <pii> G[1000005];
// 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;
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]){
n = N, k = K;
for(int i = 0; i <= n; ++i){
T.G[i].clear();
sz[i] = edgecnt[i] = exist[i] = 0;
}
for (int i = 1; i <= n - 1; i ++) {
int u = H[i][0], v = H[i][1], w = L[i];
T.G[u].insert ({v, w});
T.G[v].insert ({u, w});
}
tt = 0;
int ans = T.sol (0, -1);
return (ans == inf ? - 1 : ans);
}
// hmvncvdqdela