| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 126328 | songc | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> pii;
int N, K, ans;
vector<pii> L[202020];
LL S[202020];
int C[202020];
set<pii>* f(int u, int p){
set<pii> *M = new set<pii>, *T;
for (pii it : L[u]){
if (it.second == p) continue;
T = f(it.second, u);
T->insert(pii(-S[it.second], -C[it.second]));
S[it.second] += it.first;
C[it.second]++;
auto P = T->lower_bound(pii(K-S[it.second], -N));
if (P->first == K-S[it.second] && P != T->end()) ans = min(ans, P->second+C[it.second]);
if (M->size() < T->size()) {
swap(M, T);
swap(S[u], S[it.second]);
swap(C[u], C[it.second]);
}
for (pii v : *T) {
P = M->lower_bound(pii(K-v.first-S[it.second]-S[u], -N));
if (P->first == K-v.first-S[it.second]-S[u] && P != M->end()) ans = min(ans, P->second+v.second+C[u]+C[it.second]);
}
for (pii v : *T) M->insert(pii(v.first+S[it.second]-S[u], v.second+C[it.second]-C[u]));
T->clear();
}
return M;
}
int main(){
int u, v, w;
scanf("%d %d", &N, &K);
for (int i=1; i<N; i++){
scanf("%d %d %d", &u, &v, &w);
L[u].push_back(pii(w, v));
L[v].push_back(pii(w, u));
}
ans = N;
f(0, -1);
if (ans >= N) ans = -1;
printf("%d\n", ans);
return 0;
}