Submission #528552

#	Time	Username	Problem	Language	Result	Execution time	Memory
528552		couplefire	Parkovi (COCI22_parkovi)	C++17	110 / 110	1014 ms	34980 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second

const int N = 200005;

int n, k;
vector<pii> adj[N];
bool vis[N], park[N];

ll dfs(int v, int p, ll mid){
    if(v!=0 && (int)adj[v].size()==1)
        return 0;
    ll mn = 1e16, mx = -1e16;
    for(auto [u, w] : adj[v]){
        if(u==p) continue;
        ll val = dfs(u, v, mid);
        if(val==0ll && vis[u]){
            mn = min(mn, 0ll);
            mx = max(mx, 0ll);
            continue;
        }
        if(val+w<=0ll) vis[v] = 1, val += w;
        else if(val<0ll) val = 0;
        else val += w;
        if(val>mid){
            park[u] = 1;
            val = min(-mid+w, 0ll);
            if(-mid+w<=0ll) vis[v] = 1;
            vis[u] = 1;
        }
        mn = min(mn, val);
        mx = max(mx, val);
    }
    if(-mn>=mx) return mn;
    return mx;
}

int check(ll mid){
    memset(vis, 0, sizeof vis);
    memset(park, 0, sizeof park);
    if(dfs(0, 0, mid)>0) park[0] = 1;
    else if(!vis[0]) park[0] = 1;
    int cnt = 0;
    for(int i = 0; i<n; ++i)
        cnt += park[i];
    return cnt;
}

int main(){
    // freopen("a.in", "r", stdin);
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 0; i<n-1; ++i){
        int a, b, w;
        cin >> a >> b >> w;
        --a; --b;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    ll lo = 0, hi = 1e16;
    while(lo<hi){
        ll mid = lo+(hi-lo)/2;
        if(check(mid)<=k) hi = mid;
        else lo = mid+1;
    }
    cout << lo << '\n';
    check(lo);
    vector<int> res;
    for(int i = 0; i<n; ++i)
        if(park[i]) res.push_back(i);
    for(int i = 0; i<n; ++i)
        if(!park[i] && (int)res.size()<k)
            res.push_back(i);
    for(auto x : res)
        cout << x+1 << ' ';
    cout << '\n';
}

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