oj.uz

Submission #543528

# Submission time Handle Problem Language Result Execution time Memory
543528 2022-03-30T20:44:15 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 45192 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;

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;
                ans.pb(v);
            }

            // 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];
        ans.pb(u);
    }

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

ll dists[200005];
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);
            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(1e15);
    while (lo != hi) {
        mid = (lo + hi) / 2;
        dfs(0, 0);

        fill(dists, dists + 200005, ll(1e15));
        trav(node, ans) dists[node] = 0;
        dfs2(0, 0);
        dfs3(0, 0);

        ll max_dist = 0;
        rep(i, 0, n) {
            max_dist = max(max_dist, dists[i]);
        }

        if (max_dist > mid) ans.pb(0);

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

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

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

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 40212 KB Output is correct
2 Correct 845 ms 42508 KB Output is correct
3 Correct 756 ms 25392 KB Output is correct
4 Execution timed out 3087 ms 24624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 43168 KB Output is correct
2 Correct 815 ms 42168 KB Output is correct
3 Correct 763 ms 40364 KB Output is correct
4 Correct 761 ms 40268 KB Output is correct
5 Correct 820 ms 44364 KB Output is correct
6 Correct 880 ms 43420 KB Output is correct
7 Correct 898 ms 45192 KB Output is correct
8 Correct 829 ms 42696 KB Output is correct
9 Correct 832 ms 42444 KB Output is correct
10 Correct 801 ms 41756 KB Output is correct
11 Correct 782 ms 40376 KB Output is correct
12 Correct 880 ms 45024 KB Output is correct
13 Correct 893 ms 45120 KB Output is correct
14 Correct 864 ms 43576 KB Output is correct
15 Correct 810 ms 40980 KB Output is correct
16 Correct 778 ms 39616 KB Output is correct
17 Correct 749 ms 39364 KB Output is correct
18 Correct 818 ms 41304 KB Output is correct
19 Correct 783 ms 41908 KB Output is correct
20 Correct 822 ms 42608 KB Output is correct
21 Correct 776 ms 41668 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6484 KB Output is correct
2 Correct 7 ms 6612 KB Output is correct
3 Correct 6 ms 6612 KB Output is correct
4 Correct 7 ms 6612 KB Output is correct
5 Correct 7 ms 6484 KB Output is correct
6 Correct 6 ms 6580 KB Output is correct
7 Correct 7 ms 6576 KB Output is correct
8 Correct 8 ms 6484 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 7 ms 6576 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 8 ms 6576 KB Output is correct
13 Correct 7 ms 6612 KB Output is correct
14 Correct 6 ms 6580 KB Output is correct
15 Correct 828 ms 40212 KB Output is correct
16 Correct 845 ms 42508 KB Output is correct
17 Correct 756 ms 25392 KB Output is correct
18 Execution timed out 3087 ms 24624 KB Time limit exceeded
19 Halted 0 ms 0 KB -