| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 872036 | NgTrung2217 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define taskname ""
#define ff first
#define ss second
#define int ll
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const char el = '\n';
const char sp = ' ';
const ll inf = 1e9; //1e18;
const ll maxN = 1e6 + 5;
const ll maxK = 1e6 + 5;
int n, k;
struct Tedge
{
int u, v, w;
} e[maxN];
vector <int> adj[maxN];
int ans, ss[maxN], del[maxN], cnt[maxK];
int dfs(int u, int par = 0)
{
ss[u] = 1;
for (int i : adj[u])
{
int v = e[i].u ^ e[i].v ^ u;
if (v == par || del[v]) continue;
ss[u] += dfs(v, u);
}
return ss[u];
}
int find_centroid(int s, int u, int par = 0)
{
for (int i : adj[u])
{
int v = e[i].u ^ e[i].v ^ u;
if (v == par || del[v]) continue;
if (ss[v] * 2 > s) return find_centroid(s, v, u);
}
return u;
}
void dfs2(int add, int d, int w, int u, int par = 0)
{
if (w > k) return;
if (add == 0)
ans = min(ans, d + cnt[k - w]);
else if (add == 1)
cnt[w] = min(cnt[w], d);
else
cnt[w] = inf;
for (int i : adj[u])
{
int v = e[i].u ^ e[i].v ^ u;
if (v == par || del[v]) continue;
dfs2(add, d + 1, w + e[i].w, v, u);
}
}
void centroid_decomp(int u = 1)
{
int centroid = find_centroid(dfs(u), u);
del[centroid] = 1;
for (int i : adj[centroid])
{
int v = e[i].u ^ e[i].v ^ centroid;
if (del[v]) continue;
dfs2(0, 1, e[i].w, v);
dfs2(1, 1, e[i].w, v);
}
for (int i : adj[centroid])
{
int v = e[i].u ^ e[i].v ^ centroid;
if (del[v]) continue;
dfs2(2, 1, e[i].w, v);
}
for (int i : adj[centroid])
{
int v = e[i].u ^ e[i].v ^ centroid;
if (del[v]) continue;
centroid_decomp(v);
}
}
int32_t main ()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen(taskname".inp", "r"))
{
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
}
cin >> n >> k;
for (int i = 1;i < n;++i)
{
cin >> e[i].u >> e[i].v >> e[i].w;
adj[e[i].u].push_back(i);
adj[e[i].v].push_back(i);
}
ans = inf;
fill(cnt, cnt + k + 1, inf);
centroid_decomp();
cout << (ans == inf ? -1 : ans);
}