oj.uz

Submission #543531

# Submission time Handle Problem Language Result Execution time Memory
543531 2022-03-30T20:59:07 Z Victor Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 44276 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(1e15);
    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 6 ms 6604 KB Output is correct
2 Correct 7 ms 6612 KB Output is correct
3 Correct 7 ms 6612 KB Output is correct
4 Correct 7 ms 6484 KB Output is correct
5 Correct 7 ms 6608 KB Output is correct
6 Correct 7 ms 6612 KB Output is correct
7 Correct 7 ms 6484 KB Output is correct
8 Correct 8 ms 6604 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 8 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6608 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 7 ms 6484 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 40336 KB Output is correct
2 Correct 914 ms 41148 KB Output is correct
3 Correct 859 ms 20608 KB Output is correct
4 Execution timed out 3076 ms 20560 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 916 ms 41876 KB Output is correct
2 Correct 880 ms 40888 KB Output is correct
3 Correct 850 ms 39140 KB Output is correct
4 Correct 877 ms 39088 KB Output is correct
5 Correct 946 ms 43076 KB Output is correct
6 Correct 920 ms 42076 KB Output is correct
7 Correct 941 ms 43396 KB Output is correct
8 Correct 909 ms 42192 KB Output is correct
9 Correct 898 ms 41780 KB Output is correct
10 Correct 924 ms 41068 KB Output is correct
11 Correct 844 ms 39796 KB Output is correct
12 Correct 951 ms 44276 KB Output is correct
13 Correct 990 ms 44264 KB Output is correct
14 Correct 933 ms 42900 KB Output is correct
15 Correct 888 ms 41036 KB Output is correct
16 Correct 842 ms 39628 KB Output is correct
17 Correct 827 ms 39496 KB Output is correct
18 Correct 885 ms 41312 KB Output is correct
19 Correct 848 ms 41944 KB Output is correct
20 Correct 902 ms 42728 KB Output is correct
21 Correct 857 ms 41556 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6604 KB Output is correct
2 Correct 7 ms 6612 KB Output is correct
3 Correct 7 ms 6612 KB Output is correct
4 Correct 7 ms 6484 KB Output is correct
5 Correct 7 ms 6608 KB Output is correct
6 Correct 7 ms 6612 KB Output is correct
7 Correct 7 ms 6484 KB Output is correct
8 Correct 8 ms 6604 KB Output is correct
9 Correct 7 ms 6612 KB Output is correct
10 Correct 8 ms 6612 KB Output is correct
11 Correct 7 ms 6612 KB Output is correct
12 Correct 7 ms 6608 KB Output is correct
13 Correct 7 ms 6484 KB Output is correct
14 Correct 7 ms 6484 KB Output is correct
15 Correct 891 ms 40336 KB Output is correct
16 Correct 914 ms 41148 KB Output is correct
17 Correct 859 ms 20608 KB Output is correct
18 Execution timed out 3076 ms 20560 KB Time limit exceeded
19 Halted 0 ms 0 KB -