Submission #953370

#	Time	Username	Problem	Language	Result	Execution time	Memory
953370		efishel	Race (IOI11_race)	C++17	0 / 100	64 ms	73272 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] = MAXN; vis[dis] = timer; }
    freq[dis] = min(freq[dis], dep);
}
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 > k) 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 > k) return;
    cerr << dis << ' ' << dep << " on " << u+1 << '\n';
    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, 0, 0);
        dfs_dis(v, ctd, 0, 0);
    }
    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];
        ll w = L[i];
        u--; v--;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    solve(0);
    return ans;
}

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