| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1315447 | vlomaczk | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll M = 200'010;
ll n,kk, inf=1e7;
ll ans = inf;
vector<vector<pair<ll, ll>>> g(M);
vector<ll> par(M), sajz(M), is_off(M), depth(M);
void sajz_dfs(ll v, ll p) {
sajz[v] = 1;
par[v] = p;
for(auto[u,k] : g[v]) {
if(is_off[u] || u==p) continue;
depth[u] = depth[v] + 1;
sajz_dfs(u,v);
sajz[v] += sajz[u];
}
}
ll find_centroid(ll v, ll ts) {
for(auto[u,k] : g[v]) {
if(is_off[u]) continue;
if(u==par[v]) {
if(ts-sajz[v] > ts/2) return find_centroid(u,ts);
} else {
if(sajz[u] > ts/2) return find_centroid(u,ts);
}
}
return v;
}
map<ll, ll> mapa1, mapa2;
void calc_dfs(ll v, ll p, ll d) {
if(mapa1.find(d)==mapa1.end()) mapa1[d] = depth[v];
else mapa1[d] = min(mapa1[d], depth[v]);
if(mapa2.find(kk-d)!=mapa2.end()) ans = min(ans, mapa2[kk-d] + mapa1[d]);
for(auto[u,k] : g[v]) {
if(u==p || is_off[u]) continue;
calc_dfs(u,v,d+k);
}
}
void upd_dfs(ll v, ll p, ll d) {
if(mapa2.find(d)==mapa2.end()) mapa2[d] = mapa1[d];
else mapa2[d] = min(mapa2[d], mapa1[d]);
for(auto[u,k] : g[v]) {
if(u==p || is_off[u]) continue;
upd_dfs(u,v,d+k);
}
}
void centroid_decomp(ll v) {
sajz_dfs(v,v);
ll ctr = find_centroid(v,sajz[v]);
depth[ctr] = 0;
sajz_dfs(ctr,ctr);
mapa2[0] = 0;
for(auto[u,k] : g[ctr]) {
if(is_off[u]) continue;
calc_dfs(u,ctr,k);
upd_dfs(u,ctr,k);
}
mapa1.clear(); mapa2.clear();
is_off[ctr] = 1;
for(auto[u,k] : g[ctr]) if(!is_off[u]) centroid_decomp(u);
}
ll best_path(ll N, ll K, vector<vector<ll>> H, vector<ll> L) {
n=N; kk=K;
for(ll i=0; i<n-1; ++i) {
ll a = H[i][0];
ll b = H[i][1];
ll c = L[i];
g[a].push_back({b,c});
g[b].push_back({a,c});
}
centroid_decomp(0);
if(ans==inf) return -1;
return ans;
}