Submission #314003

#	Time	Username	Problem	Language	Result	Execution time	Memory
314003		tatyam	Race (IOI11_race)	C++17	21 / 100	669 ms	262148 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
const ll INF = 0x1fffffffffffffff;
bool chmin(ll& a, ll b){ if(a > b){ a = b; return 1; } return 0; }
bool chmax(ll& a, ll b){ if(a < b){ a = b; return 1; } return 0; }

ll k;
ll solve(vector<vector<pair<ll, ll>>> g){
    if(g.size() == 1) return INF;
    const ll n = g.size();
    vector<ll> siz(n, 1);
    ll max = 0, a, b, d;
    auto dfs_size = [&](ll from, ll at, ll dist, auto dfs) -> void {
        for(auto [i, d] : g[at]) if(i != from){
            dfs(at, i, d, dfs);
            siz[at] += siz[i];
        }
        if(siz[at] * 2 <= n && chmax(max, siz[at])){
            a = from; b = at; d = dist;
        }
    };
    dfs_size(-1, 0, 0, dfs_size);
    unordered_map<ll, ll> lower;
    vector<vector<pair<ll, ll>>> g_lower(1), g_upper(1);
    auto dfs_lower = [&](ll from, ll at, ll depth, ll dist, auto dfs) -> void {
        if(!lower.try_emplace(dist, depth).second) chmax(lower[dist], depth);
        const ll at2 = g_lower.size() - 1;
        for(auto [i, d] : g[at]) if(i != from){
            g_lower[at2].emplace_back(g_lower.size(), d);
            g_lower.push_back({{at2, d}});
            dfs(at, i, depth - 1, dist - d, dfs);
        }
    };
    dfs_lower(a, b, -1, -d, dfs_lower);
    ll ans = INF;
    auto dfs_upper = [&](ll from, ll at, ll depth, ll dist, auto dfs) -> void {
        if(lower.count(dist - k)) chmin(ans, depth - lower[dist - k]);
        const ll at2 = g_upper.size() - 1;
        for(auto [i, d] : g[at]) if(i != from){
            g_upper[at2].emplace_back(g_upper.size(), d);
            g_upper.push_back({{at2, d}});
            dfs(at, i, depth + 1, dist + d, dfs);
        }
    };
    dfs_upper(b, a, 0, 0, dfs_upper);
    chmin(ans, solve(g_lower));
    chmin(ans, solve(g_upper));
    return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
    k = K;
    vector<vector<pair<ll, ll>>> g(N);
    for(ll i = 0; i < N - 1; i++){
        const auto [a, b] = H[i];
        const int c = L[i];
        g[a].emplace_back(b, c);
        g[b].emplace_back(a, c);
    }
    return solve(g);
}

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