제출 #953389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953389		efishel	경주 (Race) (IOI11_race)	C++17	100 / 100	351 ms	72784 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
 
const ll MAXN = 1E6+16;
vector <pair <ll, ll> > adj[MAXN];
vector <char> used(MAXN, false);
vll sz(MAXN);
 
ll dfs_subsz (ll u, ll par) {
    sz[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        if (used[v]) continue;
        sz[u] += dfs_subsz(v, u);
    }
    return sz[u];
}
 
ll dfs_ctd (ll u, ll par, ll n) {
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        if (used[v]) continue;
        if (sz[v] > n/2) return dfs_ctd(v, u, n);
    }
    return u;
}
 
vll freq(MAXN, MAXN);
vll vis(MAXN, 0);
ll timer = 1;
void sett (ll dis, ll dep) {
    if (vis[dis] == timer) freq[dis] = min(freq[dis], dep);
    else { freq[dis] = dep; vis[dis] = timer; }
}
ll get (ll dis) {
    if (0 <= dis && dis < MAXN-8 && vis[dis] == timer) return freq[dis];
    return MAXN;
}
ll k;
ll ans = MAXN;
 
void dfs_calc (ll u, ll par, ll dis, ll dep) {
    if (dis > MAXN-4) return;
    ans = min(ans, get(k-dis)+dep);
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        if (used[v]) continue;
        dfs_calc(v, u, dis+w, dep+1);
    }
}
 
void dfs_dis (ll u, ll par, ll dis, ll dep) {
    if (dis > MAXN-4) return;
    sett(dis, dep);
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        if (used[v]) continue;
        dfs_dis(v, u, dis+w, dep+1);
    }
}
 
void solve (ll u) {
    ll n = dfs_subsz(u, u);
    ll ctd = dfs_ctd(u, u, n);
    used[ctd] = true;
    timer++;
    sett(0, 0);
    for (auto [v, w] : adj[ctd]) {
        if (used[v]) continue;
        dfs_calc(v, ctd, w, 1);
        dfs_dis(v, ctd, w, 1);
    }
    for (auto [v, w] : adj[ctd]) {
        if (used[v]) continue;
        solve(v);
    }
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    ll n = N;
    k = K;
    for (ll i = 0; i < n-1; i++) {
        ll u = H[i][0], v = H[i][1];
        adj[u].push_back({ v, L[i] });
        adj[v].push_back({ u, L[i] });
    }
    solve(0);
    return (ans == MAXN ? -1 : ans);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57