| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 777523 | a_aguilo | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
int n, k;
const int maxN = 200000;
vector<pair<int, int>> AdjList[maxN];
vector<int> exists;
int padre[maxN];
int subTreeSize[maxN];
void print(vector<pair<int, int>>& V){
for(pair<int, int>& pii: V){
cout << pii.first << " ";
}
cout << endl;
}
void preProcess(int node){
subTreeSize[node] = 1;
for(pair<int, int>& next: AdjList[node]){
//cout << node << " -> " << next.first << endl;
if(next.first != padre[node] && exists[next.first]){
padre[next.first] = node;
preProcess(next.first);
subTreeSize[node] += subTreeSize[next.first];
}
}
//cout << node << " " << subTreeSize[node] << endl;
}
int find_Centroid(int node, int sze){
for(int i = 0; i < AdjList[node].size(); ++i){
pair<int, int> next = AdjList[node][i];
if(next.first == padre[node] || !exists[next.first]) continue;
if(subTreeSize[next.first] > (sze/2)) {
i = -1;
node = next.first;
}
}
return node;
}
void findDistances(int node, int currDist, int numEdges, vector<pair<int, int>>& V){
if(currDist > k) return;
V.push_back({currDist, numEdges});
for(pair<int, int>& next: AdjList[node]){
if(exists[next.first] && next.first != padre[node]){
padre[next.first] = node;
findDistances(next.first, currDist+next.second, numEdges+1, V);
}
}
}
int solveSubTree(int node){
padre[node] = node;
preProcess(node);
int sze = subTreeSize[node];
node = find_Centroid(node, sze);
//cout << node << endl;
padre[node] = node;
int lengths[k+1];
fill(lengths, lengths + k + 1, 1e9);
int ans = 1e9;
for(pair<int, int>& next: AdjList[node]){
if(next.first == padre[node]) continue;
if(!exists[next.first]) continue;
padre[next.first] = node;
vector<pair<int, int>> prov;
findDistances(next.first, next.second, 1, prov);
for(pair<int, int>& val: prov){
int d = val.first;
int edges = val.second;
ans = min(ans, lengths[k - d] + edges);
}
for(pair<int, int>& val: prov){
int d = val.first;
int edges = val.second;
lengths[d] = min(lengths[d], edges);
}
/*
cout << node << " -> " << next.first << endl;
for(int i = 1; i <= k; ++i) cout << lengths[i] << " ";
cout << endl;*/
}
ans = min(ans, lengths[k]);
exists[node] = 0;
for(pair<int, int>& next: AdjList[node]){
if(exists[next.first]) ans = min(ans, solveSubTree(next.first));
}
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
exists = vector<int>(N, 1);
int a, b, c;
for(int i = 0; i < N-1; ++i){
a = H[i][0];
b = H[i][1];
c = L[i];
AdjList[a].push_back({b, c});
AdjList[b].push_back({a, c});
}
/*
for(int i = 0; i < N-1; ++i){
cout << i << '\t';
print(AdjList[i]);
}*/
int res = solveSubTree(0);
if(res == 1e9) return -1;
return res;
}
int main(){
int N, K;
cin >> N >> K;
int H[N-1][2];
int L[N-1];
for(int i = 0; i < N-1; ++i) cin >> H[i][0] >> H[i][1] >> L[i];
cout << best_path(N, K, H, L);
return 0;
}