oj.uz

Submission #533572

# Submission time Handle Problem Language Result Execution time Memory
533572 2022-03-06T10:19:15 Z kartel Parkovi (COCI22_parkovi) C++14
20 / 110
 278 ms 46512 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;
        }
        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.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 6 ms 4940 KB Output is correct
5 Correct 7 ms 4940 KB Output is correct
6 Correct 9 ms 4940 KB Output is correct
7 Correct 9 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 29 ms 4940 KB Output is correct
10 Correct 6 ms 4940 KB Output is correct
11 Correct 18 ms 5024 KB Output is correct
12 Correct 29 ms 4940 KB Output is correct
13 Correct 6 ms 5032 KB Output is correct
14 Correct 17 ms 4984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 44552 KB Output is correct
2 Correct 100 ms 45980 KB Output is correct
3 Correct 278 ms 22432 KB Output is correct
4 Correct 150 ms 14152 KB Output is correct
5 Correct 150 ms 13968 KB Output is correct
6 Correct 171 ms 14108 KB Output is correct
7 Correct 146 ms 13416 KB Output is correct
8 Correct 172 ms 14552 KB Output is correct
9 Correct 151 ms 14088 KB Output is correct
10 Correct 160 ms 14332 KB Output is correct
11 Correct 120 ms 17604 KB Output is correct
12 Correct 114 ms 18600 KB Output is correct
13 Correct 152 ms 20064 KB Output is correct
14 Correct 108 ms 18240 KB Output is correct
15 Correct 102 ms 17264 KB Output is correct
16 Correct 113 ms 18668 KB Output is correct
17 Correct 111 ms 17180 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 46512 KB Unexpected end of file - int32 expected
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 6 ms 4940 KB Output is correct
5 Correct 7 ms 4940 KB Output is correct
6 Correct 9 ms 4940 KB Output is correct
7 Correct 9 ms 4940 KB Output is correct
8 Correct 6 ms 4940 KB Output is correct
9 Correct 29 ms 4940 KB Output is correct
10 Correct 6 ms 4940 KB Output is correct
11 Correct 18 ms 5024 KB Output is correct
12 Correct 29 ms 4940 KB Output is correct
13 Correct 6 ms 5032 KB Output is correct
14 Correct 17 ms 4984 KB Output is correct
15 Correct 88 ms 44552 KB Output is correct
16 Correct 100 ms 45980 KB Output is correct
17 Correct 278 ms 22432 KB Output is correct
18 Correct 150 ms 14152 KB Output is correct
19 Correct 150 ms 13968 KB Output is correct
20 Correct 171 ms 14108 KB Output is correct
21 Correct 146 ms 13416 KB Output is correct
22 Correct 172 ms 14552 KB Output is correct
23 Correct 151 ms 14088 KB Output is correct
24 Correct 160 ms 14332 KB Output is correct
25 Correct 120 ms 17604 KB Output is correct
26 Correct 114 ms 18600 KB Output is correct
27 Correct 152 ms 20064 KB Output is correct
28 Correct 108 ms 18240 KB Output is correct
29 Correct 102 ms 17264 KB Output is correct
30 Correct 113 ms 18668 KB Output is correct
31 Correct 111 ms 17180 KB Output is correct
32 Incorrect 110 ms 46512 KB Unexpected end of file - int32 expected
33 Halted 0 ms 0 KB -