| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 419304 | iulia13 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int K = 1e6 + 5;
struct ura{
int x, c;
};
vector <ura> g[N];
int vc[K];
int sz[N], viz[N];
int n, k; int minim = K;
void dfsSize(int nod, int dad = -1)
{
sz[nod] = 1;
for (auto son : g[nod])
{
if (son.x == dad || viz[son.x])
continue;
dfsSize(son.x, nod);
sz[nod] += sz[son.x];
}
}
map <int, int> mp2;
int centroid(int nod, int dad, int newN)
{
for (auto son : g[nod])
{
if (son.x == dad || viz[son.x])
continue;
if (sz[son.x] > newN / 2)
return centroid(son.x, nod, newN);
}
return nod;
}
void dfs(int nod, int dad, int sum, int l)
{
if (sum > k)
return;
if (mp2[sum])
mp2[sum] = min(mp2[sum], l);
else
mp2[sum] = l;
for (auto son : g[nod])
{
if (son.x == dad || viz[son.x])
continue;
dfs(son.x, nod, sum + son.c, l + 1);
}
}
void divide(int root)
{
dfsSize(root);
int mid = centroid(root, -1, sz[root]);
viz[mid] = 1;
map <int, int> mp;
for (auto son : g[mid])
{
int x = son.x;
if (viz[x])
continue;
mp2.clear();
dfs(x, mid, son.c, 1);
for (auto it : mp2)
{
if (it.first == k)
minim = min(minim, it.second);
if (mp.count(k - it.first) == 0)
continue;
minim = min(minim, it.second + mp[k - it.first]);
}
for (auto it : mp2)
{
int beb = it.first;
if (mp[beb] == 0)
mp[beb] = mp2[beb];
else
mp[beb] = min(mp[beb], mp2[beb]);
}
}
for (auto son : g[mid])
if (viz[son.x] == 0)
divide(son.x);
}
int best_path(int nn, int kk, int h[][2], int l[])
{
int i;
n = nn;
k = kk;
for (i = 0; i < n - 1; i++)
{
int a = h[i][0];
int b = h[i][1];
g[a].push_back({b, l[i]});
g[b].push_back({a, l[i]});
}
divide(0);
if (minim == K)
minim = -1;
return minim;
}
int nnn, kkk;
int h[N][2];
int l[N];
int main()
{
int nnn, kkk;
cin >> nnn >> kkk;
for (int i = 0; i < nnn - 1; i++)
{
cin >> h[i][0];
cin >> h[i][1];
cin >> l[i];
}
cout << best_path(nnn, kkk, h, l);
return 0;
}