oj.uz

Submission #543533

# Submission time Handle Problem Language Result Execution time Memory
543533 2022-03-30T21:00:53 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 44368 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:164:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  164 |         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 6604 KB Output is correct
3 Correct 7 ms 6484 KB Output is correct
4 Correct 8 ms 6484 KB Output is correct
5 Correct 6 ms 6608 KB Output is correct
6 Correct 7 ms 6484 KB Output is correct
7 Correct 7 ms 6612 KB Output is correct
8 Correct 10 ms 6612 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 7 ms 6484 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 6 ms 6484 KB Output is correct
13 Correct 7 ms 6608 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 40332 KB Output is correct
2 Correct 770 ms 41292 KB Output is correct
3 Correct 735 ms 20572 KB Output is correct
4 Execution timed out 3079 ms 20516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 818 ms 41760 KB Output is correct
2 Correct 791 ms 40896 KB Output is correct
3 Correct 742 ms 39244 KB Output is correct
4 Correct 719 ms 38940 KB Output is correct
5 Correct 827 ms 43056 KB Output is correct
6 Correct 811 ms 42164 KB Output is correct
7 Correct 867 ms 43504 KB Output is correct
8 Correct 838 ms 42096 KB Output is correct
9 Correct 813 ms 41732 KB Output is correct
10 Correct 791 ms 41076 KB Output is correct
11 Correct 754 ms 39704 KB Output is correct
12 Correct 859 ms 44308 KB Output is correct
13 Correct 859 ms 44368 KB Output is correct
14 Correct 834 ms 42900 KB Output is correct
15 Correct 791 ms 41168 KB Output is correct
16 Correct 745 ms 39612 KB Output is correct
17 Correct 719 ms 39492 KB Output is correct
18 Correct 792 ms 41316 KB Output is correct
19 Correct 767 ms 42064 KB Output is correct
20 Correct 809 ms 42852 KB Output is correct
21 Correct 760 ms 41664 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 6604 KB Output is correct
3 Correct 7 ms 6484 KB Output is correct
4 Correct 8 ms 6484 KB Output is correct
5 Correct 6 ms 6608 KB Output is correct
6 Correct 7 ms 6484 KB Output is correct
7 Correct 7 ms 6612 KB Output is correct
8 Correct 10 ms 6612 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 7 ms 6484 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 6 ms 6484 KB Output is correct
13 Correct 7 ms 6608 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct
15 Correct 764 ms 40332 KB Output is correct
16 Correct 770 ms 41292 KB Output is correct
17 Correct 735 ms 20572 KB Output is correct
18 Execution timed out 3079 ms 20516 KB Time limit exceeded
19 Halted 0 ms 0 KB -