| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 969948 | _shr104 | Race (IOI11_race) | C++14 | 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>
using namespace std;
typedef long long int ll;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 2e5+7;
ll n, ans = 1e18, mn[mxn*10], cnt_mn[mxn*10], dist[mxn], h[mxn], cnt = -1, k, sz[mxn];
bool del[mxn];
vector<vector<pair<ll,ll>>> g(mxn);
void dfs_sz(ll u, ll v)
{
sz[u] = 1;
for (pair<ll,ll> i : g[u])
{
if (i.fi != v && !del[i.fi])
{
dfs_sz(i.fi,u);
sz[u] += sz[i.fi];
}
}
}
ll dfs_ctr(ll u, ll v, ll szx) {for (pair<ll,ll> i : g[u]) {if (i.fi != v && !del[i.fi] && sz[i.fi] > szx/2) {return dfs_ctr(i.fi,u,szx);}} return u;}
void get_dist(ll u, ll v)
{
for (pair<ll,ll> i : g[u])
{
if (i.fi != v && !del[i.fi])
{
h[i.fi] = h[u]+1;
dist[i.fi] = dist[u]+i.se;
// cerr << dist[i.fi] << " ";
get_dist(i.fi,u);
}
}
}
void upd_ans(ll u, ll v)
{
if (k-dist[u] > 0)
{
if (mn[k-dist[u]] != 1e18)
{
if (mn[k-dist[u]]+h[u] < ans)
{
ans = mn[k-dist[u]]+h[u];
cnt = cnt_mn[k-dist[u]]*2;
}
else cnt += cnt_mn[k-dist[u]]*2;
}
}
else if (k-dist[u] == 0)
{
if (h[u] < ans)
{
ans = h[u];
cnt = 2;
}
else cnt += 2;
}
for (pair<ll,ll> i : g[u])
{
if (i.fi != v && !del[i.fi]) upd_ans(i.fi,u);
}
}
void add(ll u, ll v)
{
if (dist[u] < k)
{
if (mn[dist[u]] > h[u])
{
mn[dist[u]] = h[u];
cnt_mn[dist[u]] = 1;
}
else cnt_mn[dist[u]]++;
}
for (pair<ll,ll> i : g[u])
{
if (i.fi != v && !del[i.fi]) add(i.fi,u);
}
}
void reset(ll u, ll v)
{
if (dist[u] < k) {mn[dist[u]] = 1e18; cnt_mn[dist[u]] = 0;}
}
void upd(ll u)
{
dist[u] = h[u] = 0; get_dist(u,u);
// cerr << "CURRENT CENTROID: " << u << '\n';
// for (ll i = 1; i <= 4; i++) cerr << h[i] << ' ' << dist[i] << '\n';
// cerr << '\n';
for (pair<ll,ll> i : g[u])
{
if (!del[i.fi])
{
// for (ll j = 1; j <= 7; j++) cout << mn[j] << ' ' << cnt_mn[j] << '\n';
upd_ans(i.fi,u); add(i.fi,u);
}
}
for (pair<ll,ll> i : g[u]) {if (!del[i.fi]) {reset(i.fi,u);}}
}
void solve(ll u)
{
dfs_sz(u,u); ll n_root = dfs_ctr(u,u,sz[u]);
upd(n_root); del[n_root] = 1;
for (pair<ll,bool> i : g[n_root]) {if (!del[i.fi]) solve(i.fi);}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
cin >> n >> k;
for (ll i= 1; i < n; i++)
{
ll a, b, c; cin >> a >> b >> c;
a++; b++; g[a].pb({b,c}); g[b].pb({a,c});
}
for (ll i = 1; i <= 1e6; i++) {mn[i] = 1e18;}
solve(1);
if (ans == 1e18) cout << -1;
else cout << ans;
}