Submission #314010

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

race

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

int k;
int solve(vector<vector<pair<int, int>>> g){
    if(g.size() == 1) return INF;
    const int n = g.size();
    int mx = 0, a, b, d;
    vector<int> siz(n, 1);
    {
        auto dfs = [&](int from, int at, int 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(mx, siz[at])){
                a = from; b = at; d = dist;
            }
        };
        dfs(-1, 0, 0, dfs);
    }
    unordered_map<int, int> lower;
    vector<vector<pair<int, int>>> g_lower(1), g_upper(1);
    g_lower.reserve(siz[b]);
    g_upper.reserve(n - siz[b]);
    lower.reserve(siz[b]);
    siz.clear();
    siz.shrink_to_fit();
    auto dfs_lower = [&](int from, int at, int depth, int dist, auto dfs) -> void {
        if(!lower.try_emplace(dist, depth).second) chmax(lower[dist], depth);
        const int 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, max(dist - d, -INF), dfs);
        }
    };
    dfs_lower(a, b, -1, -d, dfs_lower);
    int ans = INF;
    auto dfs_upper = [&](int from, int at, int depth, int dist, auto dfs) -> void {
        if(lower.count(dist - k)) chmin(ans, depth - lower[dist - k]);
        const int 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, min(dist + d, INF), dfs);
        }
    };
    dfs_upper(b, a, 0, 0, dfs_upper);
    g.clear();
    g.shrink_to_fit();
    {
        unordered_map<int, int> a(0);
        lower.swap(a);
    }
    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<int, int>>> g(N); // 8MB
    for(int 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);
    }
    int ans = solve(g);
    if(ans == INF) return -1;
    return ans;
}

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