| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1014054 | Tienthanh2007 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int maxn = 2e5 + 5;
int n, k;
vector <pii> adj[maxn];
int child[maxn];
bool del[maxn];
int cnt[1000005], mx_depth = 0;
int res = 1e9;
void count_child(int u, int par){
child[u] = 1;
for(auto [w, v] : adj[u]){
if(v == par || del[v]) continue;
count_child(v, u);
child[u] += child[v];
}
}
int find_centroid(int u, int par, int sz){
for(auto [w, v] : adj[u]){
if(v == par || del[v]) continue;
if(child[v] >= sz / 2)
return find_centroid(v, u, sz);
}
return u;
}
void get_cnt(int u, int par, bool filling, int Rank, int depth){
if(depth > k) return;
mx_depth = max(mx_depth, depth);
if(filling) cnt[depth] = min(cnt[depth], Rank);
else res = min(res, cnt[k - depth] + Rank);
for(auto [w, v] : adj[u]){
if(v == par || del[v]) continue;
get_cnt(v, u, filling, Rank + 1, depth + w);
}
}
void decomposition(int u){
count_child(u, -1);
int sz = child[u];
int centroid = find_centroid(u, -1, sz);
del[centroid] = 1;
mx_depth = 0;
for(auto [w, v] : adj[centroid]){
if(del[v]) continue;
get_cnt(v, centroid, false, 1, w);
get_cnt(v, centroid, true, 1, w);
}
fill(cnt, cnt + mx_depth, 1e9);
for(auto [w, v] : adj[centroid]){
if(del[v]) continue;
decomposition(v);
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n - 1; i ++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({w, v});
adj[v].push_back({w, u});
}
fill(cnt, cnt + 1000000, 1e9);
decomposition(0);
if(res == 1e9) res = -1;
cout << res;
return 0;
}