| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 474473 | disastah | 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.
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+1e8;
const ll linf=4e18+18;
const int N=2e5;
int n, k, h[N], ans=inf; ll dep[N];
map<ll,int> dp[N];
vector<ar<int,2>> g[N];
int get(int v, ll x) {
return (dp[v].find(x)!=dp[v].end()?dp[v][x]:inf);
}
void dfs(int v, int p=-1) {
dp[v][dep[v]]=h[v];
for (auto &[u,c] : g[v]) {
if (u!=p) {
h[u]=h[v]+1, dep[u]=dep[v]+c;
dfs(u,v);
if (dp[u].size()>dp[v].size()) swap(dp[v],dp[u]);
for (auto &[x,dh] : dp[u]) {
ans=min(ans,dh+get(v,k-x+2*dep[v])-2*h[v]);
}
for (auto &[x,dh] : dp[u]) {
if (dp[v].find(x)==dp[v].end()) dp[v][x]=dh;
else dp[v][x]=min(dp[v][x],dh);
}
}
}
}
int best_path(int n0, int k0, int h[][2], int l[]) {
n=n0, k=k0;
for (int i=0; i<n-1; ++i) {
g[h[i][0]].push_back({h[i][1],l[i]});
g[h[i][1]].push_back({h[i][0],l[i]});
}
dfs(0);
return (ans<n?ans:-1);
}
/*signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef disastah
cout << "Output\n\n";
#endif
int tt=1;
// cin >> tt;
while (tt--) {
solve();
cout << "\n";
}
}