| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 385604 | negar_a | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <ll, ll>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
const ll maxn = 1e5 + 5, N = 1e6 + 5;
vector <pii> adj[maxn];
ll w[maxn], sz[maxn];
ll h[maxn], d[maxn], mn[N];
ll n, k;
ll inf = INT_MAX, ans = INT_MAX;
bool dead[maxn];
void dfs(ll v, ll p = -1){
sz[v] = 1;
for(auto u : adj[v]){
if(u.F != p && !dead[u.F]){
d[u.F] = d[v] + w[u.S];
h[u.F] = h[v] + 1;
dfs(u.F, v);
sz[v] += sz[u.F];
}
}
}
ll find_centroid(ll v, ll p, ll z){
for(auto u : adj[v]){
if(u.F != p && !dead[u.F] && sz[u.F] > z / 2){
return find_centroid(u.F, v, z);
}
}
return v;
}
void get(ll v, ll p = -1){
if(k - d[v] >= 0){
ans = min(mn[k - d[v]] + h[v], ans);
}
for(auto u : adj[v]){
if(u.F != p && !dead[u.F]){
get(u.F, v);
}
}
}
void upd(ll v, ll p = -1){
if(k - d[v] >= 0){
mn[d[v]] = min(h[v], mn[d[v]]);
}
for(auto u : adj[v]){
if(u.F != p && !dead[u.F]){
upd(u.F, v);
}
}
}
void clr(ll v, ll p = -1){
mn[d[v]] = inf;
for(auto u : adj[v]){
if(u.F != p && !dead[u.F]){
upd(u.F, v);
}
}
}
void solve(ll v){
dfs(0);
ll c = find_centroid(v, -1, sz[v]);
dead[c] = true;
h[c] = d[c] = 0;
dfs(c);
for(auto x : adj[c]){
ll u = x.F;
if(!dead[u]){
get(u, c);
upd(u, c);
}
}
ans = min(ans, mn[k]);
clr(c);
for(auto x : adj[c]){
if(!dead[x.F]){
solve(x.F);
}
}
}
///*
int best_path(ll N, ll K, ll H[][2], ll L[]){
n = N;
k = K;
for(ll i = 0; i < n-1; i++)
{
ll x = H[i][0], y = H[i][1];
adj[x].push_back({y, i});
adj[y].push_back({x, i});
}
for(ll i = 0; i < n-1; i++)
w[i] = L[i];
for(ll i = 0; i < N - 2; i ++){
mn[i] = inf;
}
solve(0);
if(ans >= inf)
ans = -1;
return ans;
}
//*/
/*
int main(){
fast_io;
cin >> n >> k;
for(ll i = 0; i < n - 1; i ++){
ll x, y;
cin >> x >> y;
adj[x].pb({y, i});
adj[y].pb({x, i});
}
for(ll i = 0; i < n - 1; i ++){
cin >> w[i];
}
for(ll i = 0; i < N - 2; i ++){
mn[i] = inf;
}
solve(0);
if(ans >= inf){
cout << -1;
}
else{
cout << ans;
}
return 0;
}
*/