| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 986251 | chautanphat | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1, W = 1e6 + 1;
int n, k, child[N], f[W], ans = N;
bool del[N];
vector<pair<int, int>> a[N];
void cntSize(int u, int pre = 0)
{
child[u] = 1;
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first;
if (v == pre || del[v]) continue;
cntSize(v, u);
child[u] += child[v];
}
}
int centroid(int u, int sz, int pre = 0)
{
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first;
if (v != pre && !del[v] && child[v] > sz/2) return centroid(v, sz, u);
}
return u;
}
void cal(int u, int dis, int mode, int pre = 0, int h = 1)
{
if (dis > k) return;
if (!mode)
ans = min(ans, h+f[k-dis]);
else f[dis] = min(f[dis], h);
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first, w = a[u][i].second;
if (del[v] || v == pre) continue;
cal(v, dis+w, mode, u, h+1);
}
}
void reset(int u, int dis, int pre = 0)
{
f[dis] = N;
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first, w = a[u][i].second;
if (del[v] || v == pre) continue;
reset(v, dis+w, u);
}
}
void decompose(int u)
{
cntSize(u);
int root = centroid(u, child[u]);
del[root] = 1;
for (int i = 0; i < (int)a[root].size(); i++)
{
int v = a[root][i].first, w = a[root][i].second;
if (del[v]) continue;
cal(v, w, 0);
cal(v, w, 1);
}
for (int i = 0; i < (int)a[root].size(); i++)
{
int v = a[root][i].first, w = a[root][i].second;
if (del[v]) continue;
reset(v, w);
}
for (int i = 0; i < (int)a[root].size(); i++)
if (!del[a[root][i].first]) decompose(a[root][i].first);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= k; i++) f[i] = N;
for (int i = 1; i < n; i++)
{
int u, v, l;
cin >> u >> v >> l;
a[++u].push_back({++v, l});
a[v].push_back({u, l});
}
decompose(1);
cout << (ans == N ? -1 : ans);
return 0;
}