| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1147416 | aminjon__ | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl '\n'
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
#include "race.h"
int best_path(int N, int K, int H[][2], int L[])
{
vector<vector<pair<ll,ll>>>rebr(N+1);
for(int i = 0;i < N-1;i++){
rebr[H[i][0]].push_back({H[i][1],L[i]});
rebr[H[i][1]].push_back({H[i][0],L[i]});
}
ll ans = LLONG_MAX;
auto dfs =[&](ll x , ll p , ll sum , ll depth , auto &&dfs){
set< pair<ll,ll> > Suffix;
Suffix.insert({sum , depth});
for(auto g: rebr[x]){
if(g.first==p)continue;
auto govno = dfs(g , x , sum+g.second ,depth+1, dfs);
if(Suffix.size() < govno.size()){
swap(govno, Suffix);
}
for(auto g: govno){
Suffix.insert(g);
}
}
for(auto g: Suffix){
if(g.first == sum+K){
ans = min(g.second-depth ,ans);
continue;
}
auto r = Suffix.upper_bound({sum+sum+K - g.first , 0});
if(r != Suffix.end()){
ans = min(ans , g.second+r->second - (depth*2) );
}
}
return Suffix;
};
dfs(1 , 0 , 0 , 0 , dfs);
return (ans == LLONG_MAX ? -1 : ans);
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}