| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 941327 | Icelast | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 4e18+9;
int n, k;
vector<pair<ll, ll>> adj[maxn];
void inp(){
cin >> n >> k;
ll u, v, w;
for(int i = 1; i < n; i++){
cin >> u >> v >> w;
u++; v++;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
}
map<ll, ll> f[maxn];
ll dr[maxn], er[maxn];
void glen(int u, int p, ll d, int e){
dr[u] = d; er[u] = e;
for(auto it : adj[u]){
int v = it.first;
ll w = it.second;
if(v == p) continue;
glen(v, u, d+w, e+1);
}
}
ll ans = INF;
void merg(int u, int v){
if(f[u].size() < f[v].size()){
swap(f[u], f[v]);
}
for(auto it : f[v]){
if(f[u].find(k-it.first+2*dr[u]) == f[u].end()) continue;
ans = min(ans, it.second+f[u][k-it.first+2*dr[u]]-2*er[u]);
}
for(auto it : f[v]){
if(f[u].find(it.first) == f[u].end()){
f[u][it.first] = it.second;
continue;
}
f[u][it.first] = min(f[u][it.first], it.second);
}
}
void dfs(int u, int p){
f[u][dr[u]] = er[u];
for(auto it : adj[u]){
int v = it.first;
ll w = it.second;
if(v == p) continue;
dfs(v, u);
merg(u, v);
}
// cout << u << " " << er[u] << "\n";
// for(auto it : f[u]){
// cout << it.first-dr[u] << " " << it.second-er[u] << "\n";
// }
// cout << "\n";
}
void solve(){
glen(1, 1, 0, 0);
dfs(1, 1);
if(ans == INF) ans = -1;
cout << ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
solve();
}