| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 605494 | mychecksedad | 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.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int M = 2e5 + 100;
struct Edge{
int next, len;
};
int n, k, sub[M], best = M;
ll val[M];
vector<int> g[M];
map<int, pair<bool, int>> a[M];
void dfs(int v, int p){
int mx = 0, big = -1;
for(Edge e: g[v]){
if(e.next != p && sub[e.next] > mx){
mx = sub[e.next];
big = e.next;
}
}
for(Edge e: g[v]){
if(e.next != p && e.next != big)
dfs(e.next, v);
}
if(big > -1)
dfs(big, v), a[v].swap(a[big]);
if(a[v][val[v]].first == 0){
a[v][val[v]].first = 1;
}else a[v][val[v]].second = 0;
for(Edge e: g[v]){
if(e.next != big && e.next != p){
for(auto p: a[e.next]){
if(a[v][k - p.first + 2 * val[v]].first == 1) best = min(best, p.second.second + a[v][k - p.first + 2 * val[v]].second);
if(a[v][p.first].first == 0){
a[v][p.first] = {1, p.second.second};
}else a[v][val[v]].second = min(a[v][val[v]].second, p.second.second);
}
}
}
}
void init(int v, int p, ll d){
sub[v] = 1;
val[v] = d;
for(Edge e: g[v]){
if(e.next != p){
dfs(e.next, v, d + e.len);
sub[v] += sub[e.next];
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
best = N;
n = N;
k = K;
Edge e;
for(int i = 0; i < n-1; ++i){
e.next = H[i][1];
e.len = L[i];
g[H[i][0]].pb(e);
e.next = H[i][0];
g[H[i][1]].pb(e);
}
init(1, 0, 0);
dfs(1, 0);
return best;
}