| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 905078 | a_l_i_r_e_z_a | 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.
// In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())
const int maxn = 2e5 + 5, maxk = 1e6 + 5;
const int inf = 1e9 + 7;
ll n, k, ans = inf;
vector<pll> adj[maxn];
map<ll, ll> mn[maxn];
void dfs(int v = 0, int h = 0, ll d = 0, int p = -1){
mn[v].insert(mp(d, h));
for(auto [u, w]: adj[v]){
if(u == p) continue;
dfs(u, h + 1, d + w, v);
if(mn[u].size() > mn[v].size()) swap(mn[u], mn[v]);
for(auto w: mn[u]){
ll x = k + 2 * d - w.F;
auto it = mn[v].find(x);
if(it != mn[v].end()) smin(ans, w.S + (*it).S - 2 * h);
}
for(auto w: mn[u]){
auto it = mn[v].find(w.F);
if(it != mn[v].end()) smin((*it).S, w.S);
else mn[v].insert(w);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
fill(mn, mn + maxk, inf);
for(int i = 0; i < n - 1; i++){
int u = H[i][0], v = H[i][1], w = L[i];
adj[u].pb(mp(v, w));
adj[v].pb(mp(u, w));
}
dfs();
return (ans >= inf ? -1 : ans);
}
// int32_t main()
// {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// cin >> n >> k;
// for(int i = 0; i < n - 1; i++){
// int u, v, w; cin >> u >> v >> w;
// adj[u].pb(mp(v, w));
// adj[v].pb(mp(u, w));
// }
// dfs();
// cout << (ans >= inf ? -1 : ans) << '\n';
// return 0;
// }