| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 172414 | cgiosy | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<n; i++)
using namespace std;
constexpr int INF=0x3f3f3f3f;
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
int N, K, m=INF;
cin>>N>>K;
vector<bool> V(N);
vector<int> C(N, 1), D(K+1, INF), P(N, -1), X;
vector<vector<pair<int, int>>> G(N);
rep(i, 1, N) {
int x, y, z;
cin>>x>>y>>z;
G[x].push_back({y, z});
G[y].push_back({x, z});
}
#define ITER(i) for(auto[j,w]:G[i]) if(j!=P[i] && !V[j])
function<void(int)> cnt=[&](int i) {
ITER(i) P[j]=i, cnt(j), C[i]+=C[j];
};
function<int(int, int)> cent=[&](int i, int n) {
ITER(i) if(C[j]>n/2) {
P[i]=j;
C[j]+=C[i]-=C[j];
return cent(j, n);
}
return i;
};
function<void(int, int, int)> f=[&](int i, int d, int k) {
X.push_back(d);
m=min(m, k+D[K-d]);
D[d]=min(D[d], k);
ITER(i) if(d+w<=K && k+1<m) f(j, d+w, k+1);
};
function<void(int, int)> cd=[&](int i, int p) {
P[i=cent(i, C[i])]=p;
V[i]=true, D[0]=0;
f(i, 0, 0);
for(int x:X) D[x]=INF;
X.clear();
ITER(i) cd(j, i);
};
cnt(0);
cd(0, -1);
cout<<(m==INF?-1:m);
}