oj.uz

Submission #533555

# Submission time Handle Problem Language Result Execution time Memory
533555 2022-03-06T09:46:12 Z kartel Parkovi (COCI22_parkovi) C++14
10 / 110
 107 ms 46404 KB 
#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;
        }
        dp[v] = max(dp[u] + w, dp[v]);
        dfs(u, 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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 6 ms 4940 KB Output is correct
4 Correct 5 ms 5024 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 9 ms 5028 KB Output is correct
7 Correct 10 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 29 ms 5036 KB Output is correct
10 Correct 7 ms 4940 KB Output is correct
11 Correct 19 ms 5012 KB Output is correct
12 Correct 39 ms 4940 KB Output is correct
13 Correct 6 ms 5028 KB Output is correct
14 Correct 16 ms 5024 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 44604 KB Integer 0 violates the range [1, 187509]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 46404 KB Integer 0 violates the range [1, 196048]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 6 ms 4940 KB Output is correct
4 Correct 5 ms 5024 KB Output is correct
5 Correct 5 ms 4940 KB Output is correct
6 Correct 9 ms 5028 KB Output is correct
7 Correct 10 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 29 ms 5036 KB Output is correct
10 Correct 7 ms 4940 KB Output is correct
11 Correct 19 ms 5012 KB Output is correct
12 Correct 39 ms 4940 KB Output is correct
13 Correct 6 ms 5028 KB Output is correct
14 Correct 16 ms 5024 KB Output is correct
15 Incorrect 84 ms 44604 KB Integer 0 violates the range [1, 187509]
16 Halted 0 ms 0 KB -