| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1287647 | islam_2010 | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int sz = 2e5+5;
const int inf = 1e9 + 7;
vector<pair<int, int>> g[sz];
vector<pair<int, int>> len[sz];
vector<int> sub(sz);
vector<bool> isremoved(sz);
vector<pair<int, int>> anc[sz];
map<int, int> mp;
int mn = sz, mx;
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 = -1, int d = 0, int dist = 0, int k, bool calc){
if(d > k){
return;
}
if(calc){
if(mp[k-d]){
for(auto i: len[k-d]){
mn = min(mn, i.first+dist);
}
}
}else {
mp[d]++;
len[d].push_back({dist, node});
mx = max(mx, d);
}
for(auto i: g[node]){
if(isremoved[i.first] || i.first == p) continue;
search(i.first, node, d + i.second, dist+1, k, calc);
}
}
void build(int node, int k){
int cent = get_centroid(node, subtree_size(node));
mp[0] = 1;
isremoved[cent] = true;
mx = 0;
mn = inf;
search(cent, cent, 0, 0, k, false);
search(cent, cent, 0, 0, k, true);
for(int i = 0; i < mx; i++){
len[i].clear();
}mp.clear();
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[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
return mn;
}