Submission #540625

#	Time	Username	Problem	Language	Result	Execution time	Memory
540625		AlperenT	Parkovi (COCI22_parkovi)	C++17	110 / 110	1915 ms	44056 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const long long INF = 2e18 + 5;

int n, k, a, b, c;

long long l, r, m, park[N], nongood[N];

bool ispark[N];

vector<pair<int, long long>> tree[N];

void dfs(int v, int p, int pw, long long x){
    if(tree[v].size() == 1) nongood[v] = 0;

    for(auto e : tree[v]){
        if(e.first != p){
            dfs(e.first, v, e.second, x);

            park[v] = min(park[v], park[e.first] + e.second);
        }
    }

    for(auto e : tree[v]){
        if(e.first != p){
            if(nongood[e.first] + e.second + park[v] > x){
                nongood[v] = max(nongood[v], nongood[e.first] + e.second);
            }
        }
    }

    if(park[v] > x) nongood[v] = max(nongood[v], 0ll);

    if(nongood[v] + pw > x) ispark[v] = true, park[v] = 0, nongood[v] = -INF;
}

bool check(long long x){
    memset(ispark, 0, sizeof(ispark)), fill(park, park + N, INF), fill(nongood, nongood + N, -INF);

    dfs(1, 0, 0, x);

    if(park[1] > x || (nongood[1] + park[1] > x)) ispark[1] = true;

    return accumulate(ispark + 1, ispark + n + 1, 0) <= k;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n >> k;

    for(int i = 1; i <= n - 1; i++){
        cin >> a >> b >> c;

        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }

    l = -1, r = INF;

    while(r - l > 1){
        m = l + (r - l) / 2;

        if(check(m)) r = m;
        else l = m;
    }

    check(r);

    vector<int> v;

    for(int i = 1; i <= n; i++) if(ispark[i]) v.push_back(i);

    for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);

    cout << r << "\n";

    for(auto i : v) cout << i << " ";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:77:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     for(int i = 1; i <= n; i++) if(!ispark[i] && v.size() < k) v.push_back(i);
      |                                                  ~~~~~~~~~^~~

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