Submission #533572

#	Time	Username	Problem	Language	Result	Execution time	Memory
533572		kartel	Parkovi (COCI22_parkovi)	C++14	20 / 110	278 ms	46512 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define sz(x) (int)x.size()
#define el "\n"
using namespace std;
typedef long long ll;

const int N = 2e5 + 500;

ll ans = 1e18;
int best, n, k;
vector <pair <int, int> > g[N];
ll dp[N];
ll d[25][25];

void dfs(int v, int pr) {
    for (auto p : g[v]) {
        int u = p.F, w = p.S;
        if (u == pr) {
            continue;
        }
        dfs(u, v);
        dp[v] = max(dp[u] + w, dp[v]);
    }
}

void go(int v, int pr, ll longest) {
    multiset <ll> se;
    for (auto u : g[v]) {
        if (u.F == pr) {
            continue;
        }
        se.insert(dp[u.F] + u.S);
    }

    if (max(longest, dp[v]) < ans) {
        ans = max(longest, dp[v]);
        best = v;
    }
    for (auto u : g[v]) {
        if (u.F == pr) {
            continue;
        }
        se.erase(se.find(dp[u.F] + u.S));
        ll nlongest = longest;
        if (sz(se)) {
            nlongest = max(nlongest, *se.rbegin());
        }
        go(u.F, v, nlongest + u.S);
        se.insert(dp[u.F] + u.S);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w; u--; v--;
        g[v].pb({u, w});
        g[u].pb({v, w});
    }

    if (n <= 20) {
        ll acur = 1e18;
        vector <int> ans;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = 1e18;
            }
        }
        for (int i = 0; i < n; i++) {
            for (auto j : g[i]) {
                int w = j.S;
                int u = j.F;

                d[i][u] = w;
            }
        }
        for (int m = 0; m < n; m++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    d[i][j] = min(d[i][j], d[i][m] + d[m][j]);
                }
            }
        }
        for (int mask = 0; mask < (1 << n); mask++) {
            if (__builtin_popcount(mask) != k) {
                continue;
            }
            vector <int> cur;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    cur.pb(i);
                }
            }

            ll mx = 0;
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    ll mn = 1e18;
                    for (auto j : cur) {
                        mn = min(mn, d[i][j]);
                    }
                    mx = max(mx, mn);
                }
            }
            if (mx < acur) {
                acur = mx;
                ans = cur;
            }
        }
        cout << acur << el;
        for (auto x : ans) {
            cout << x + 1 << " ";
        }
        return 0;
    }
    dfs(0, -1);
    go(0, -1, 0);

    cout << ans << el << best + 1;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60