| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 830616 | Johann | 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 "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define pii pair<ll, ll>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define mll map<ll, ll>
#define vmll vector<mll>
void root(vvpii & adj, int v, int p, vi & height, vi & dist) {
height[v] = height[p] + 1;
ll u,d;
for (pii e : adj[v]) {
tie(u,d) = e;
if (u == p) continue;
dist[u] = dist[v] + d;
root(adj, u, v, height, dist);
}
}
void InOrUpdate(mll & DV, ll dv, ll hv) {
if (DV.find(dv) == DV.end()) DV[dv] = hv;
else DV[dv] = min(DV[dv], hv);
}
void solve(vvpii & adj, int v, vi & dist, vi & height, vmll & distVert, ll & ans, int K) {
int maxSub = -1;
for (pii e : adj[v]) {
ll u = e.first;
if (height[u] <= height[v]) continue; // parent; // distances können auch null sein...
solve(adj, u, dist, height, distVert, ans, K);
if (maxSub == -1 || distVert[maxSub].size() < distVert[u].size()) maxSub = u;
}
if (maxSub != -1) { // not a leaf!
ll k = K + 2 * dist[v];
swap(distVert[v], distVert[maxSub]);
for (pii e : adj[v]) {
ll u = e.first;
if (height[u] < height[v] && u != maxSub) continue; // parent or maxSubTree
for (pii bla : distVert[u]) {
if (distVert[v].find(k - bla.first) != distVert[v].end()) {
ans = min(ans, bla.second + distVert[v][k - bla.first] - 2 * height[v]);
}
}
for (pii bla : distVert [u]) InOrUpdate(distVert[v], bla.first, bla.second);
distVert[u].clear();
}
}
InOrUpdate(distVert[v], dist[v], height[v]);
if (distVert[v].find(K + dist[v]) != distVert[v].end()) ans = min(ans, distVert[v][K + dist[v]] - height[v]);
// printf("Vertex: %d\n", v); for (pii bla : distVert[v]) { printf("%d - %d\n", bla.first, bla.second); } cout << endl;
}
int best_path(int N, int K, int H[][2], int L[]){
vvpii adj(N);
for (int i = 0,a,b; i < N-1; ++i) {
a = H[i][0];
b = H[i][1];
adj[a].push_back({b, L[i]});
adj[b].push_back({a, L[i]});
}
vi height(N, 0), dist(N, 0);
root(adj, 0, 0, height, dist);
vmll distVert(N); // { dist[v], height[v] } pairs!
ll ans = INT_MAX;
solve(adj, 0, dist, height, distVert,ans, K);
return (ans == INT_MAX) ? -1 : ans;
}