Submission #671162

#	Time	Username	Problem	Language	Result	Execution time	Memory
671162		neki	Parkovi (COCI22_parkovi)	C++14	110 / 110	1369 ms	45136 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define vc vector

using namespace std;

int main() {
    ll n, k; cin >> n >> k;
    vc<vc<pair<ll, ll>>> edg(n+1);
    ll sum=0;
    for(ll i=1;i<n;++i){
        ll a, b, w;cin >> a >> b >> w;
        sum+=w;
        edg[a].emplace_back(b, w);
        edg[b].emplace_back(a, w);
    }
    ll l=0, r=sum, cnt=0;
    vc<ll> ans(n+1, 0);
    function<ll (ll)> solve=[&](ll d){
        ans.assign(n+1, 0);
        cnt=0;
        function<pair<ll, ll> (ll, ll, ll)> dfs=[&](ll u, ll p, ll w){
            ll bm=0, m, M=0;
            for(auto v: edg[u])if(v.first!=p){
                auto q=dfs(v.first, u, v.second);
                if(q.first){
                    if(bm) m=min(m, q.second);
                    else bm=1, m=q.second;
                }
                else M=max(M, q.second);
            }
            if(p==-1){
                if(bm && m+M<=d) return make_pair(0LL, 0LL);
                ++cnt; ans[u]=1;
                return make_pair(1LL, 0LL);
            }
            
            if(bm){
                if(m+M<=d) return make_pair(1LL, m+w);
                if(M+w<=d) return make_pair(0LL, M+w);
                ++cnt;ans[u]=1;
                //dodamo park v u
                return make_pair(1LL, w);
            }
            else{
                if(M+w<=d) return make_pair(0LL, M+w);
                ++cnt;ans[u]=1;
                //dodamo park v u
                return make_pair(1LL, w);
            }
        };
        dfs(1, -1, 0);
        return cnt<=k;
    };
    if(n==1){
        cout << 0 << endl;
        cout << 1 << endl;
        return 0;
    }
    /*for(ll i=0;i<sum;++i){
        cout << i<<": " <<solve(i)<<endl;
    }*/
    while(l<r){
        ll mid=(l+r)/2;
        if(solve(mid)) r=mid;
        else l=mid+1;
    }
    cout << l << endl;solve(l);
    for(ll i=1;i<=n;++i) if(cnt<k && ans[i]==0) ans[i]=1, ++cnt;
    for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |     for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
      |     ^~~
Main.cpp:70:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |     for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
      |                                                      ^~~~

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