| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1287648 | islam_2010 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int sz = 2e5+5;
const int inf = 1e9 + 7;
vector<pair<int, int>> g[sz];
vector<int> sub(sz);
vector<bool> isremoved(sz);
int mn;
int subtree_size(int node, int p = -1){
sub[node] = 1;
for(auto i: g[node]){
if(isremoved[i.first] || i.first == p) continue;
sub[node] += subtree_size(i.first, node);
}return sub[node];
}
int get_centroid(int node, int stsz, int p = -1){
for(auto i: g[node]){
if(isremoved[i.first] || i.first == p) continue;
if(sub[i.first] * 2 > stsz){
return get_centroid(i.first, stsz, node);
}
}return node;
}
void search(int node, int p, int d, int dist, int k, vector<pair<int,int>>& vals) {
if (d > k) return;
vals.push_back({d, dist});
for (auto i : g[node]) {
if (isremoved[i.first] || i.first == p) continue;
search(i.first, node, d + i.second, dist + 1, k, vals);
}
}
void build(int node, int k){
int stsz = subtree_size(node);
int cent = get_centroid(node, stsz);
isremoved[cent] = true;
map<int,int> mp;
mp[0] = 0;
for(auto i: g[cent]){
if(isremoved[i.first]) continue;
vector<pair<int,int>> vals;
search(i.first, cent, i.second, 1 , k, vals);
for(auto [d, dist]: vals){
if(mp.count(k-d)){
mn = min(mn, mp[k-d]+dist);
}
}
for(auto [d, dist]: vals){
if(!mp.count(d)){
mp[d] = dist;
}else {
mp[d] = min(mp[d], dist);
}
}
}
for(auto i: g[cent]){
if(!isremoved[i.first]){
build(i.first, k);
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
for (int i = 0; i <= N; i++) {
g[i].clear();
isremoved[i] = false;
}
for(int i = 0; i < N-1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}mn = inf;
build(0, K);
return (mn == inf ? -1 : mn);
}
int main() {
int N = 4, K = 11;
int h[3][2] = {{0, 1}, {1, 2}, {2, 3}};
int L[3] = {5, 6, 7};
cout << best_path(N, K, h, L);
}