oj.uz

Submission #696694

# Submission time Handle Problem Language Result Execution time Memory
696694 2023-02-07T04:29:55 Z minhnhatnoe Parkovi (COCI22_parkovi) C++14
0 / 110
 644 ms 41740 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 644 ms 39936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 641 ms 41740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -