oj.uz

Submission #541248

# Submission time Handle Problem Language Result Execution time Memory
541248 2022-03-22T20:20:46 Z Victor Parkovi (COCI22_parkovi) C++17
30 / 110
 1561 ms 52416 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) {
    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, 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 << " max_dist = " << max_dist[u] << " to_park = " << to_park[u] << endl
    //     << endl;
}

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);

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

    mid = lo;
    dfs(0, 0,0);
    set<ll> ans;
    trav(val, solution) ans.insert(val);

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5020 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 35856 KB Output is correct
2 Correct 418 ms 40940 KB Output is correct
3 Correct 403 ms 25180 KB Output is correct
4 Correct 1535 ms 23168 KB Output is correct
5 Correct 1425 ms 22472 KB Output is correct
6 Correct 1436 ms 22604 KB Output is correct
7 Correct 1532 ms 21436 KB Output is correct
8 Correct 1561 ms 22404 KB Output is correct
9 Correct 1511 ms 22728 KB Output is correct
10 Correct 1548 ms 23076 KB Output is correct
11 Incorrect 1057 ms 24836 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 428 ms 37228 KB Output is correct
2 Correct 419 ms 40460 KB Output is correct
3 Correct 396 ms 38688 KB Output is correct
4 Correct 389 ms 38556 KB Output is correct
5 Correct 491 ms 51304 KB Output is correct
6 Correct 478 ms 46400 KB Output is correct
7 Correct 505 ms 48524 KB Output is correct
8 Correct 435 ms 41144 KB Output is correct
9 Correct 423 ms 40780 KB Output is correct
10 Correct 411 ms 40172 KB Output is correct
11 Correct 407 ms 38804 KB Output is correct
12 Correct 531 ms 52416 KB Output is correct
13 Correct 499 ms 49864 KB Output is correct
14 Correct 473 ms 45876 KB Output is correct
15 Correct 385 ms 39364 KB Output is correct
16 Correct 382 ms 37836 KB Output is correct
17 Correct 377 ms 37792 KB Output is correct
18 Correct 399 ms 39556 KB Output is correct
19 Correct 456 ms 48796 KB Output is correct
20 Correct 432 ms 47388 KB Output is correct
21 Correct 427 ms 44956 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5020 KB Output isn't correct
8 Halted 0 ms 0 KB -