oj.uz

Submission #541272

# Submission time Handle Problem Language Result Execution time Memory
541272 2022-03-22T21:16:50 Z Victor Parkovi (COCI22_parkovi) C++17
10 / 110
 3000 ms 61220 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) {
    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;
                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(1e15);
    while (lo != hi) {
        mid = (lo + hi) / 2;
        dfs(0, 0);

        fill(dists, dists + 200005, ll(1e15));
        set<pll> pq;
        trav(val, solution) pq.emplace(0, val), dists[val] = 0;

        while (!pq.empty()) {
            ll u, d;
            tie(d, u) = *pq.begin();
            pq.erase(pq.begin());

            trav(edge, graph[u]) {
                ll v, w;
                tie(v, w) = edge;
                if (d + w >= dists[v]) continue;

                pq.erase({dists[v], v});
                dists[v] = d + w;
                pq.insert({dists[v], v});
            }
        }

        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);
    fill(dists, dists + 200005, ll(1e16));
    set<ll> ans;
    trav(val, solution) ans.insert(val);

    set<pll> pq;
    trav(val, solution) pq.emplace(0, val), dists[val] = 0;

    while (!pq.empty()) {
        ll u, d;
        tie(d, u) = *pq.begin();
        pq.erase(pq.begin());

        trav(edge, graph[u]) {
            ll v, w;
            tie(v, w) = edge;
            if (d + w >= dists[v]) continue;

            pq.erase({dists[v], v});
            dists[v] = d + w;
            pq.insert({dists[v], v});
        }
    }

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

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 37392 KB Output is correct
2 Correct 983 ms 38252 KB Output is correct
3 Execution timed out 3060 ms 32984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2054 ms 38812 KB Output is correct
2 Correct 2001 ms 37908 KB Output is correct
3 Correct 1045 ms 36428 KB Output is correct
4 Correct 919 ms 36280 KB Output is correct
5 Correct 2647 ms 61220 KB Output is correct
6 Execution timed out 3007 ms 45668 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6484 KB Output is correct
2 Correct 10 ms 6616 KB Output is correct
3 Correct 9 ms 6484 KB Output is correct
4 Correct 10 ms 6612 KB Output is correct
5 Correct 8 ms 6612 KB Output is correct
6 Correct 11 ms 6484 KB Output is correct
7 Correct 9 ms 6612 KB Output is correct
8 Correct 11 ms 6528 KB Output is correct
9 Correct 9 ms 6608 KB Output is correct
10 Correct 9 ms 6484 KB Output is correct
11 Correct 9 ms 6612 KB Output is correct
12 Correct 10 ms 6484 KB Output is correct
13 Correct 9 ms 6612 KB Output is correct
14 Correct 10 ms 6608 KB Output is correct
15 Correct 911 ms 37392 KB Output is correct
16 Correct 983 ms 38252 KB Output is correct
17 Execution timed out 3060 ms 32984 KB Time limit exceeded
18 Halted 0 ms 0 KB -