Submission #696694

#	Time	Username	Problem	Language	Result	Execution time	Memory
696694		minhnhatnoe	Parkovi (COCI22_parkovi)	C++14	0 / 110	644 ms	41740 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct result{
    ll farthest_blank;
    ll closest_park;
};
const ll MAX = 1e18;
vector<vector<pair<int, ll>>> g;
result dfs(vector<int> &chosen, int v, int p, ll k){
    result r({-MAX, MAX});
    vector<result> c;
    for (pair<int, ll> e: g[v]){
        if (e.first == p) continue;
        result nxt = dfs(chosen, e.first, v, k);
        nxt.farthest_blank += e.second;
        nxt.closest_park += e.second;
        if (nxt.farthest_blank > k){
            nxt.farthest_blank = -MAX;
            nxt.closest_park = e.second;
            chosen.push_back(e.first);
        }
        r.closest_park = min(r.closest_park, nxt.closest_park);
        c.push_back(nxt);
    }
    bool need = false;
    for (result &x: c){
        if (x.farthest_blank + r.closest_park > k){
            need = true;
            break;
        }
    }
    if (need){
        chosen.push_back(v);
        r.farthest_blank = LLONG_MIN;
        r.closest_park = 0;
    }
    else{
        if (r.closest_park > k)
            r.farthest_blank = max(r.farthest_blank, 0LL);
    }
    return r;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    g.resize(n);
    for (int i=1; i<n; i++){
        int a, b, w; cin >> a >> b >> w;
        a--, b--;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }
    ll bl = 0, br = 1000000000LL * n;
    while (bl < br){
        ll bm = (bl+br)>>1;
        vector<int> chosen;
        result r = dfs(chosen, 0, -1, bm);
        if (r.farthest_blank > bm){
            chosen.push_back(0);
        }
        if (chosen.size() > k) bl = bm+1;
        else br = bm;
    }
    vector<int> chosen;
    result r = dfs(chosen, 0, -1, bl);
    if (r.farthest_blank > bl){
        chosen.push_back(0);
    }
    cout << bl << "\n";
    vector<bool> a(n);
    for (int v: chosen) a[v] = true;
    int add = k - chosen.size();
    for (int i=0; i<n; i++){
        if (a[i]){
            cout << i+1 << " ";
        }
        if (add){
            cout << i+1 << " ";
            add--;
        }
    }
    cout << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:64:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |         if (chosen.size() > k) bl = bm+1;
      |             ~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60