Submission #681310

#	Time	Username	Problem	Language	Result	Execution time	Memory
681310		badont	Race (IOI11_race)	C++17	100 / 100	1295 ms	62136 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using LL = long long;
const LL INF = 1e9;
using namespace std;
using pii = pair<LL, LL>;

#define pb push_back

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif


int best_path(int N, int K, int H[][2], int L[]) {
    
    LL ans = INF;
    vector e(N, vector<pii>());
    for (LL i = 0; i < N - 1; i++) {
        LL x = H[i][0], y = H[i][1], d = L[i];
        e[x].pb({y, d});
        e[y].pb({x, d});
    }

    //debug(e);

    vector<bool> v(N);
    vector<LL> sub(N);
    auto cen_decomp = [&](auto cen_decomp, LL g, LL SZ) -> void {
        auto dfs_sub = [&](auto dfs_sub, LL g, LL p) -> void {
            sub[g] = 1;
            for (auto [u, d] : e[g]) if (u != p && !v[u]) {
                dfs_sub(dfs_sub, u, g);
                sub[g] += sub[u];
            }
        };

        auto find_cen = [&](auto find_cen, LL g, LL p) -> LL {
            for (auto [u, d] : e[g]) if (u != p && !v[u]) {
                if (sub[u] * 2 >= SZ) 
                    return find_cen(find_cen, u, g);
            }
            return g;
        };

        dfs_sub(dfs_sub, g, -1);
        g = find_cen(find_cen, g, -1);
        dfs_sub(dfs_sub, g, -1);

        //debug(g);

        v[g] = 1;
        map<LL, LL> dp;
        auto fill_dp = [&](auto fill_dp, LL g, LL p, LL L, LL d) -> void {
            if (!dp.count(L)) {
                dp[L] = d;
            } else {
                dp[L] = min(dp[L], (LL)d); 
            }

            for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
                fill_dp(fill_dp, u, g, L + nl, d + 1);
            }
        };

        auto compare_dp = [&](auto compare_dp, LL g, LL p, LL L, LL d) -> void {
            if (dp.count(K - L)) {
                ans = min(ans, d + dp[K - L]);
            }   

            for (auto [u, nl] : e[g]) if (!v[u] && u != p) {
                compare_dp(compare_dp, u, g, L + nl, d + 1);
            }
        };

        dp[0] = 0;
        for (auto [u, d] : e[g]) if (!v[u]) {
            compare_dp(compare_dp, u, g, d, 1);
            fill_dp(fill_dp, u, g, d, 1);
        }

        for (auto [u, d] : e[g]) if (!v[u]) {
            cen_decomp(cen_decomp, u, sub[u]);
        }
    };

    cen_decomp(cen_decomp, 0, N);

    return (ans >= INF ? -1 : ans);
}

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