| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 781413 | taitruong270 | 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.
/*==============================================================================================================
__ __ _____ ______ _______
| | | | / __ \ / _____| / ______|
__| |__ __| |__ |_| | | | | | |
|__| __| |__| __| | | | |____ | |_____
| | _____ _ | | ____ __ __ ____ _____ _____ / / \ ___ \ | ___ \
| | / _ \ | | | | / _/ | | | | / _ \ / __ \ / _ \ / / | | | | | |
| |_ | |_| | | | | |_ | | | |_| | | |_| | | | | | | |_| | / /___ ____| | | |___| |
\____\ \____/| |_| \____\ |_| \_____/ \_____/ |_| |_| \____ | |______| |______/ \_______/
| |
__/ |
|___/
Pratice, practice, and practice
I hated every minute of training, but I said, ‘Don’t quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali
You may not be the best, but must be the most effort
Noi dau + Suy ngam = Tien bo
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll mod = 1e9+7;
ll n, k, h[200005][2], l[200005], ans=1e18, dist[200005], sum[200005];
vector<pair<ll, ll>> adj[200005];
map<ll, ll> info[200005];
void prepare(ll u, ll p, ll d, ll s)
{
info[u][s]=d;
dist[u]=d;
sum[u]=s;
for (auto [v, w]: adj[u]) if (v!=p) prepare(v, u, d+1, s+w);
}
void small_to_large_merge(ll u, ll p)
{
for (auto [v, w]: adj[u]) if (v!=p)
{
small_to_large_merge(v, u);
if (info[u].size()<info[v].size()) info[u].swap(info[v]);
for (auto [s, d]: info[v])
if (info[u].find(k+2*sum[u])!=info[u].end())
ans=min(ans, info[u][k+2*sum[u]-s]+d-2*dist[u]);
for (auto [s, d]: info[v])
if (info[u].find(s)==info[u].end())
info[u][s]=d;
else
info[u][s]=min(info[u][s], d);
}
}
ll best_path(ll n, ll k, ll h[][2], ll l[])
{
for (ll i=0; i<n-1; i++)
{
ll u=h[i][0], v=h[i][1], w=l[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
prepare(0, -1, 0, 0);
small_to_large_merge(0, -1);
if (ans==1e18) ans=-1;
return ans;
}