Submission #1246892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246892		stanirina	Parkovi (COCI22_parkovi)	C++20	0 / 110	119 ms	3484 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n,k;
vector<int> w;

bool proveri(int dist){
    int cnt=0ll;
    int i=0ll;
    int sum=0ll;
    while(i<n-1ll){
        if(sum+w[i]>dist){
            sum=0ll;
            cnt++;
            if(cnt%2==0)i++;
        }
        else{
            i++;
            sum+=w[i];
        }
    }
    cnt++;
    if((cnt+1)/2>k)return false;
    return true;
}

int32_t main()
{
    cin>>n>>k;
    w.resize(n-1);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        cin>>w[i];
    }
    int maxedge=0ll;
    int l=0ll;
    int r=100000000000000000ll;
    while(l<=r){
        int mid=l+(r-l)/2ll;
        //cout<<mid<<endl;
        if(proveri(mid))r=mid-1ll;
        else l=mid+1ll;
    }
    cout<<l<<endl;
    vector<int> vis(n,0);
    int cnt=0ll;
    int i=0ll;
    int sum=0ll;
    int ans=0ll;
    while(i<n-1ll){
        if(sum+w[i]>l){
            sum=0ll;
            cnt++;
            if(cnt%2==0)i++;
            else{ cout<<i+1<<' ';vis[i]=1;ans++;}
        }
        else{
            i++;
            sum+=w[i];
        }
    }
    if(cnt%2ll==0ll){cout<<n<<' ';ans++;vis[n-1]=1;}
    int br=0ll;
    for(int i=0;i<k-ans;i++){
        while(vis[br]==1)br++;
        cout<<br+1ll<<' ';
        br++;
    }

    return 0;
}

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