| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 12910 | gs14004 | Race (IOI11_race) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[200005];
int ret = 1e9;
int size[200005], maxtree[200005];
int kill[200005];
int k;
vector<int> new_vis;
int dfs(int p, int pa){
if(kill[p]) return 0;
new_vis.push_back(p);
int cs = 1;
int maxv = 0;
for (int i=0; i<graph[p].size(); i++) {
if(graph[p][i].second == pa) continue;
int t = dfs(graph[p][i].second,p);
maxv = max(t,maxv);
cs += t;
}
maxtree[p] = maxv;
return size[p] = cs;
}
int get_mid(int p){
new_vis.clear();
memset(size,0,sizeof(size));
memset(maxtree,0,sizeof(maxtree));
int full = dfs(p,-1);
int mid_pos = 0, mid_res = 0;
for (int i=0; i<new_vis.size(); i++) {
maxtree[new_vis[i]] = max(maxtree[new_vis[i]],full - size[new_vis[i]]);
if(mid_res < maxtree[new_vis[i]]){
mid_pos = new_vis[i];
mid_res = maxtree[mid_pos];
}
}
return mid_pos;
}
vector<int> solve(int p){
int mid = get_mid(p);
kill[mid] = 1;
vector<int> v(k+1,1e9);
v[0] = 0;
for (int i=0; i<graph[mid].size(); i++) {
if(kill[graph[mid][i].second]) continue;
vector<int> u = solve(graph[mid][i].second);
int l = graph[mid][i].first;
for (int j=0; j<=k - l; j++) {
ret = min(ret,v[k-j-l] + u[j] + 1);
}
for (int j=0; j<=k - l; j++) {
v[j+l] = min(v[j+l],u[j] + 1);
}
}
return v;
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i=0; i<N-1; i++) {
graph[H[i][0]].push_back(pi(L[i],H[i][1]));
graph[H[i][1]].push_back(pi(L[i],H[i][0]));
}
k = K;
solve(0);
return ret;
}
int main(){
int n,k;
scanf("%d %d",&n,&k);
int h[200005][2], l[200005];
for (int i=0; i<n-1; i++) {
scanf("%d %d %d",&h[i][0],&h[i][1],&l[i]);
}
printf("%d",best_path(n,k,h,l));
}