Submission #681305

#	Time	Username	Problem	Language	Result	Execution time	Memory
681305		badont	Race (IOI11_race)	C++17	0 / 100	1 ms	212 KiB

race

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

const int INF = 1e9;
using namespace std;
using pii = pair<int, int>;
using LL = long long;
#define pb push_back

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

    vector<bool> v(N), sub(N);
    auto cen_decomp = [&](auto cen_decomp, int g, int SZ) -> void {
        auto dfs_sub = [&](auto dfs_sub, int g, int 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, int g, int p) -> void {
            for (auto [u, d] : e[g]) if (u != p && !v[u]) {
                if (sub[u] * 2 >= SZ) 
                    return find_cen(find_cen, u, g);
            }
        };

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

        v[g] = 1;
        map<LL, LL> dp;
        auto fill_dp = [&](auto fill_dp, int g, int p, int L, int d) {
            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, int g, int p, int L, int d) {
            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);
            }
        };

        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]);
        }
    };

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

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:21:10: warning: variable 'cen_decomp' set but not used [-Wunused-but-set-variable]
   21 |     auto cen_decomp = [&](auto cen_decomp, int g, int SZ) -> void {
      |          ^~~~~~~~~~

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