oj.uz

Submission #533577

# Submission time Handle Problem Language Result Execution time Memory
533577 2022-03-06T10:31:31 Z kartel Parkovi (COCI22_parkovi) C++14
10 / 110
 529 ms 47924 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;

vector <pair <int, int> > g[N];
ll dp[N], cur, best, d[N];
vector <int> ans;
set <pair <ll, int> > se;
bool mk[N];
int n, k;

void dfs(int v, int pr) {
    dp[v] = 0;
    for (auto p : g[v]) {
        int u = p.F, w = p.S;
        if (u == pr || mk[u]) {
            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 || mk[u.F]) {
            continue;
        }
        se.insert(dp[u.F] + u.S);
    }

    if (max(longest, dp[v]) < cur) {
        cur = max(longest, dp[v]);
        best = v;
    }
    for (auto u : g[v]) {
        if (u.F == pr || mk[u.F]) {
            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);
    }
}

void add(int root, ll w) {
    cur = 1e18;
    dfs(root, -1);
    go(root, -1, w);
    se.insert({cur, best});
}

ll calc() {
    for (int i = 1; i <= n; i++) {
        d[i] = 1e18;
    }
    set <pair <ll, int> > se;
    for (auto x : ans) {
        d[x] = 0;
        se.insert({0, x});
    }
    while (sz(se)) {
        int v = se.begin() -> S;
        se.erase(se.begin());
        for (auto to : g[v]) {
            int u = to.F, w = to.S;
            if (d[u] > d[v] + w) {
                d[u] = d[v] + w;
                se.insert({d[u], u});
            }
        }
    }
    ll ret = 0;
    for (int i = 1; i <= n; i++) {
        ret = max(ret, d[i]);
    }
    return ret;
}

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;
        g[v].pb({u, w});
        g[u].pb({v, w});
    }

    add(1, 0);
    while (k > 0 && sz(se)) {
        k--;
        int del = se.rbegin() -> S;
        se.erase(--se.end());
        mk[del] = 1;
        ans.pb(del);
        for (auto to : g[del]) {
            int u = to.F;
            if (!mk[u]) {
                add(u, to.S);
            }
        }
    }
    cout << calc() << el;
    for (auto x : ans) {
        cout << x << " ";
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 46016 KB Output is correct
2 Correct 119 ms 47176 KB Output is correct
3 Correct 529 ms 40676 KB Output is correct
4 Correct 325 ms 16128 KB Output is correct
5 Correct 408 ms 15908 KB Output is correct
6 Correct 268 ms 15828 KB Output is correct
7 Correct 270 ms 15936 KB Output is correct
8 Correct 359 ms 16308 KB Output is correct
9 Correct 311 ms 15800 KB Output is correct
10 Correct 283 ms 16092 KB Output is correct
11 Correct 231 ms 18452 KB Output is correct
12 Correct 181 ms 19264 KB Output is correct
13 Correct 240 ms 20716 KB Output is correct
14 Correct 218 ms 19012 KB Output is correct
15 Correct 178 ms 18124 KB Output is correct
16 Correct 174 ms 19268 KB Output is correct
17 Correct 187 ms 17880 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 47924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB Output isn't correct
2 Halted 0 ms 0 KB -