| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 896133 | starchan | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e9
#define MX (int)2e5+5
#define LMX (int)1e6+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int n, k;
vector<in> adj[MX];
int sz[MX];
bool cut[MX];
void calc_subtree(int u, int p)
{
sz[u] = 1;
for(auto [v, w]: adj[u])
{
if(v==p)
continue;
if(cut[v])
continue;
calc_subtree(v, u);
sz[u]+=sz[v];
}
return;
}
int centroid(int root, int u, int p)
{
for(auto [v, w]: adj[u])
{
if(cut[v])
continue;
if(v==p)
continue;
if(2*sz[v] > sz[root])
return centroid(root, v, u);
}
return u;
}
vector<int> curr;
vector<int> on;
vector<int> best(LMX, INF);
int ans = INF;
void ritul(int u, int p, int lvl, int dist)
{
if(dist > k)
return;
ans = min(ans, lvl+best[k-dist]);
for(auto [v, w]: adj[u])
{
if((dist+w) > k)
continue;
ritul(v, u, lvl+1, dist+w);
}
return;
}
void ritul2(int u, int p, int lvl, int dist)
{
if(dist > k)
return;
curr.pb(dist);
best[dist] = min(best[dist], lvl);
for(auto [v, w]: adj[u])
{
if((dist+w) > k)
continue;
ritul2(v, u, lvl+1, dist+w);
}
return;
}
void centroid_decomp(int u)
{
calc_subtree(u, -1);
int root = centroid(u, u, -1);
cut[root] = 1;
curr.clear();
for(auto [v, w]: adj[root])
{
if(cut[v])
continue;
ritul(v, root, 1, w);
ritul2(v, root, 1, w);
}
for(int t: curr)
best[t] = INF;
for(auto [v, w]: adj[root])
{
if(cut[v])
continue;
centroid_decomp(v);
}
return;
}
int best_path(int N, int K, int h[][2], int L[])
{
n = N;
k = K;
for(int i = 1; i <= n; i++)
adj[i].clear();
for(int i = 0; i < n-1; i++)
{
int u = h[i][0];
int v = h[i][1];
u++;
v++;
int l = L[i];
adj[u].pb({v, l});
adj[v].pb({u, l});
}
best[0] = 0;
centroid_decomp(1);
if(ans == INF)
ans = -1;
return ans;
}
signed main()
{
int V, KK;
cin >> V >> KK;
int h[V-1][2];
int L[V-1];
for(int i = 0; i < V-1; i++)
cin >> h[i][0] >> h[i][1] >> L[i];
int ok = best_path(V, KK, h, L);
cout << ok << endl;
return 0;
}