Submission #417961

#	Time	Username	Problem	Language	Result	Execution time	Memory
417961		OttoTheDino	Race (IOI11_race)	C++17	9 / 100	267 ms	56876 KiB

race

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,s,e)                          for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                         for (ll i = s; i >= e; --i)
#define pb                                  push_back
#define fi                                  first
#define se                                  second
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
 
const ll mxn = 3e5;
ll ans = LLONG_MAX, dep[mxn], hdep[mxn], sz[mxn], bot[mxn], k;
vii neibs[mxn];
map<ll, ll> deep[mxn];
 
void get_depth (ll u, ll prev) {
    sz[u] = 1;
    for (ii vd : neibs[u]) {
        ll v = vd.fi, d = vd.se;
        if (v == prev) continue;
        dep[v] = dep[u]+d;
        hdep[v] = hdep[u]+1;
        get_depth (v, u);
        sz[u] += sz[v];
    }
}
 
void dfs (ll u, ll prev) {
    ll heavy = -1, ma = 0;
    for (ii vd : neibs[u]) {
        ll v = vd.fi;  
        if (v == prev) continue;
        dfs (v, u);
        if (sz[v] > ma) {
            ma = sz[v];
            heavy = v;
        }
    }
 
    if (heavy==-1) {
        bot[u] = u;
        deep[u][dep[u]] = hdep[u]; 
        return;
    }
 
    bot[u] = bot[heavy];
 
    for (ii vd : neibs[u]) {
        ll v = vd.fi;
        if (v == prev || v == heavy) continue;
 
        for (ii deps : deep[bot[v]]) {
            ll real_dep = deps.fi, high_dep = deps.se;
            ll need_dep = k+2*dep[u]-real_dep;
            if (deep[bot[u]][need_dep]) ans = min(ans, high_dep+deep[bot[u]][need_dep]-2*hdep[u]);
        }
 
        for (ii deps : deep[bot[v]]) {
            ll real_dep = deps.fi, high_dep = deps.se;
            if (!deep[bot[u]][real_dep] || high_dep < deep[bot[u]][real_dep]) deep[bot[u]][real_dep] = high_dep;
        }
    }
 
    ll need_dep = k+dep[u];
    if (deep[bot[u]][need_dep]) ans = min(ans, deep[bot[u]][need_dep]-hdep[u]);
    if (!deep[bot[u]][dep[u]] || hdep[u] < deep[bot[u]][dep[u]]) deep[bot[u]][dep[u]] = hdep[u];
}
 
int best_path (int n, int ok, int h[][2], int l[]) {
    k = ok;
    rep (i,0,n-2) {
        ll a = h[i][0], b = h[i][1], c = l[i];
        neibs[a].pb({b,c}), neibs[b].pb({a,c});
    }
 
    get_depth(0,-1);
 
    dfs (0, -1);
 
    return (ans==LLONG_MAX?-1:ans);
}

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