oj.uz

Submission #543534

# Submission time Handle Problem Language Result Execution time Memory
543534 2022-03-30T21:02:27 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 44288 KB 
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int k, n;
vpll graph[200005];
ll mid, max_dist[200005], to_park[200005], need[200005];
vll ans;

int cnt=0;
bool bla=0;
ll all_max_dist = 0;
ll dists[200005];

void dfs(ll u, ll p) {
    max_dist[u] = 0;
    to_park[u] = ll(1e16);
    need[u] = 0;

    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dfs(v, u);

            need[u] += need[v];

            max_dist[v] += w;
            to_park[v] += w;

            if (max_dist[v] > mid) {
                max_dist[v] = -1e16;
                to_park[v] = w;
                ++need[u];
                // cout << "u = " << u + 1 << " v = " << v + 1 << endl;
                dists[v]=0;
                if(bla)ans.pb(v);
                ++cnt;
            }

            // cout<<max_dist[u]<<" "<<to_park[u]<<" "<<max_dist[v]<<" "<<to_park[v]<<endl;
            if (max_dist[u] + to_park[v] <= mid) max_dist[u] = ll(-1e16);
            if (max_dist[v] + to_park[u] > mid && max_dist[v] > max_dist[u]) max_dist[u] = max_dist[v];
            if (to_park[v] < to_park[u]) to_park[u] = to_park[v];
        }
    }

    if (!u && to_park[u] > mid) {
        ++need[u];
        if(bla)ans.pb(u);
        dists[u]=0;
        ++cnt;
    }

    // cout << "u = " << u + 1 << " p = " << p + 1 << " max_dist = " << max_dist[u] << " to_park = " << to_park[u] << endl;
    // cout << "ans = " << need[u] << endl << endl;
}

void dfs2(int u, int p) {
    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dfs2(v, u);
            dists[u] = min(dists[u], dists[v] + w);
        }
    }
}

void dfs3(int u, int p) {
    trav(edge, graph[u]) {
        ll v, w;
        tie(v, w) = edge;
        if (v != p) {
            dists[v] = min(dists[v], dists[u] + w);
            all_max_dist = max(all_max_dist, dists[v]);
            dfs3(v, u);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin >> n >> k;
    rep(i, 1, n) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[--u].emplace_back(--v, w);
        graph[v].emplace_back(u, w);
    }

    ll lo = 0, hi = ll(1e14);
    while (lo != hi) {
        mid = (lo + hi) / 2;
        fill(dists, dists + 200005, ll(1e15));
        cnt=0;
        dfs(0, 0);

        all_max_dist = 0;
        dfs2(0, 0);
        dfs3(0, 0);

        if (all_max_dist > mid) ++cnt;

        if (cnt <= k)
            hi = mid;
        else
            lo = mid + 1;
        // debug(sz(ans));
        // cout << endl;
    }

    fill(dists, dists + 200005, ll(1e16));
    bla=1;
    cnt=0;
    mid = lo;
    dfs(0, 0);
    trav(node, ans) dists[node] = 0;
    dfs2(0, 0);
    dfs3(0, 0);

    all_max_dist = 0;
    rep(i, 0, n) all_max_dist = max(all_max_dist, dists[i]);
    // debug(all_max_dist);

    if (all_max_dist > mid) {
        ans.pb(0);
        dists[0] = 0;
    }

    rep(i, 0, n) {
        if (sz(ans) == k) break;
        if (dists[i]) ans.pb(i);
    }

    cout << mid << endl;
    trav(val, ans) cout << val + 1 << ' ';
    cout << endl;
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:162:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  162 |         if (sz(ans) == k) break;
      |                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6484 KB Output is correct
2 Correct 6 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6612 KB Output is correct
7 Correct 5 ms 6596 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 5 ms 6484 KB Output is correct
10 Correct 6 ms 6484 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 8 ms 6560 KB Output is correct
13 Correct 6 ms 6484 KB Output is correct
14 Correct 6 ms 6612 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 40328 KB Output is correct
2 Correct 746 ms 41252 KB Output is correct
3 Correct 915 ms 20568 KB Output is correct
4 Execution timed out 3100 ms 20580 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 41864 KB Output is correct
2 Correct 730 ms 40892 KB Output is correct
3 Correct 693 ms 39188 KB Output is correct
4 Correct 710 ms 39164 KB Output is correct
5 Correct 735 ms 43056 KB Output is correct
6 Correct 749 ms 42092 KB Output is correct
7 Correct 782 ms 43392 KB Output is correct
8 Correct 761 ms 42092 KB Output is correct
9 Correct 741 ms 41784 KB Output is correct
10 Correct 727 ms 41072 KB Output is correct
11 Correct 705 ms 39792 KB Output is correct
12 Correct 793 ms 44288 KB Output is correct
13 Correct 813 ms 44252 KB Output is correct
14 Correct 785 ms 42936 KB Output is correct
15 Correct 737 ms 41044 KB Output is correct
16 Correct 708 ms 39620 KB Output is correct
17 Correct 703 ms 39440 KB Output is correct
18 Correct 793 ms 41324 KB Output is correct
19 Correct 750 ms 42228 KB Output is correct
20 Correct 836 ms 43248 KB Output is correct
21 Correct 790 ms 42112 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6484 KB Output is correct
2 Correct 6 ms 6484 KB Output is correct
3 Correct 6 ms 6484 KB Output is correct
4 Correct 6 ms 6612 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6612 KB Output is correct
7 Correct 5 ms 6596 KB Output is correct
8 Correct 6 ms 6484 KB Output is correct
9 Correct 5 ms 6484 KB Output is correct
10 Correct 6 ms 6484 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 8 ms 6560 KB Output is correct
13 Correct 6 ms 6484 KB Output is correct
14 Correct 6 ms 6612 KB Output is correct
15 Correct 714 ms 40328 KB Output is correct
16 Correct 746 ms 41252 KB Output is correct
17 Correct 915 ms 20568 KB Output is correct
18 Execution timed out 3100 ms 20580 KB Time limit exceeded
19 Halted 0 ms 0 KB -