| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1294750 | abode_at25 | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long int
#define what(x) cout << (#x) << ": " << x << '\n';
#define prec(ans) cout << fixed << setprecision(9) << ans << endl
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 1e6 + 10;
ll inf = 1e15;
vector<pair<ll, ll>> adj[N + 1];
ll sub[N + 1];
bool vis[N + 1];
ll ans = inf;
ll k;
ll dep[N + 1];
ll weight[N + 1];
ll mn[N + 1];
void build(ll i, ll p)
{
sub[i] = 1;
for (auto [u, w] : adj[i])
{
if (u == p || vis[u])
continue;
build(u, i);
sub[i] += sub[u];
}
}
ll get_cen(ll i, ll p, ll cnt)
{
for (auto [u, w] : adj[i])
{
if (u == p || vis[u])
continue;
if (sub[u] > cnt / 2)
return get_cen(u, i, cnt);
}
return i;
}
vector<ll> subs;
vector<ll> v;
void get(ll i, ll p)
{
v.pb(i);
subs.pb(weight[i]);
if (k >= weight[i])
ans = min(ans, mn[k - weight[i]] + dep[i]);
for (auto [u, w] : adj[i])
{
if (vis[u] || u == p)
continue;
dep[u] = dep[i] + 1;
weight[u] = weight[i] + w;
get(u, i);
}
}
void dfs(ll i)
{
build(i, i);
ll cen = get_cen(i, i, sub[i]);
vis[cen] = 1;
dep[cen] = 0;
weight[cen] = 0;
mn[0] = 0;
subs.clear();
ans = inf;
// cout << cen << endl;
for (auto [u, w] : adj[cen])
{
if (vis[u])
continue;
dep[u] = 1;
weight[u] = w;
get(u, i);
// cout<<u<<' ';
// cout << x << ' ' << weight[x] << endl;
for (auto x : v)
{
if (weight[x] <= k)
mn[weight[x]] = min(mn[weight[x]], dep[x]);
}
v.clear();
}
// cout << endl;
for (auto x : subs)
{
if (x <= k)
mn[x] = inf;
}
for (auto [u, w] : adj[cen])
{
if (vis[u])
continue;
dfs(u);
}
}
ll best_path(ll n, ll K, ll H[][2], ll L[])
{
k=K;
ll a, b;
// cin >> a >> b;
vector<pair<ll, ll>> v;
for (int i = 0; i <= k; i++)
mn[i] = inf;
for (int i = 1; i <= n; i++)
adj[i].clear(), vis[i] = 0;
for (int i = 0; i < n - 1; i++)
{
a = H[i][0] + 1;
b = H[i][1] + 1;
v.pb({a, b});
// cout<<a<<' '<<b<<endl;
}
for (int i = 0; i < n - 1; i++)
{
ll c = L[i];
// cout<<c<<endl;
a = v[i].fi;
b = v[i].se;
adj[a].pb({b, c});
adj[b].pb({a, c});
}
dfs(1);
return (ans != inf ? ans : -1);
}