oj.uz

Submission #541270

# Submission time Handle Problem Language Result Execution time Memory
541270 2022-03-22T21:05:21 Z Victor Parkovi (COCI22_parkovi) C++17
10 / 110
 3000 ms 41996 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];
vll solution;
ll mid, max_dist[200005], to_park[200005], need[200005];

void dfs(ll u, ll p, int depth, ll weight) {
    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, depth + 1, w);

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

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

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

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(1e16);
    while (lo != hi) {
        mid = (lo + hi) / 2;
        dfs(0, 0, 0, 0);

        fill(dists, dists + 200005, ll(1e16));
        trav(val, solution) dfs2(val, val, 0);

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

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

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

    mid = lo;
    dfs(0, 0, 0, 0);
    fill(dists, dists + 200005, ll(1e16));
    set<ll> ans;
    trav(val, solution) ans.insert(val), dfs2(val, val, 0);

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

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

    rep(i, 0, n) {
        if (sz(ans) == k) break;
        ans.insert(i);
    }

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

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 8 ms 6612 KB Output is correct
3 Correct 8 ms 6616 KB Output is correct
4 Correct 8 ms 6568 KB Output is correct
5 Correct 7 ms 6564 KB Output is correct
6 Correct 8 ms 6612 KB Output is correct
7 Correct 7 ms 6612 KB Output is correct
8 Correct 7 ms 6612 KB Output is correct
9 Correct 8 ms 6568 KB Output is correct
10 Correct 7 ms 6612 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 8 ms 6696 KB Output is correct
13 Correct 7 ms 6568 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 666 ms 40464 KB Output is correct
2 Correct 707 ms 41676 KB Output is correct
3 Execution timed out 3089 ms 22732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2473 ms 41996 KB Output is correct
2 Correct 2702 ms 41360 KB Output is correct
3 Correct 771 ms 39628 KB Output is correct
4 Correct 705 ms 39456 KB Output is correct
5 Execution timed out 3105 ms 40664 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6612 KB Output is correct
2 Correct 8 ms 6612 KB Output is correct
3 Correct 8 ms 6616 KB Output is correct
4 Correct 8 ms 6568 KB Output is correct
5 Correct 7 ms 6564 KB Output is correct
6 Correct 8 ms 6612 KB Output is correct
7 Correct 7 ms 6612 KB Output is correct
8 Correct 7 ms 6612 KB Output is correct
9 Correct 8 ms 6568 KB Output is correct
10 Correct 7 ms 6612 KB Output is correct
11 Correct 7 ms 6484 KB Output is correct
12 Correct 8 ms 6696 KB Output is correct
13 Correct 7 ms 6568 KB Output is correct
14 Correct 7 ms 6612 KB Output is correct
15 Correct 666 ms 40464 KB Output is correct
16 Correct 707 ms 41676 KB Output is correct
17 Execution timed out 3089 ms 22732 KB Time limit exceeded
18 Halted 0 ms 0 KB -