Submission #1096098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096098		0pt1mus23	Parkovi (COCI22_parkovi)	C++14	0 / 110	204 ms	78712 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long int
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 2e5 + 23 ,
            inf = 1e10,
            L = 31 ;
vector<pair<int,int>> graph[sze];
vector<int> alst;
int dp[sze][2];
void dfs(int node,int par,int mid){
    for(auto [a,b]:graph[node]){
        if(a!=par){
            dfs(a,node,mid);
            dp[node][0] = min(dp[node][0],dp[a][0] + b);
            if(dp[a][1] + b <= mid){
                dp[node][1]=max(dp[node][1],dp[a][1] + b);
            }
            else{
                // cout<<mid<<" => "<<a<<endl;
                alst.pb(a);
                dp[node][0]=min(dp[node][0],b);
            }

        }
    }
    if(dp[node][0] + dp[node][1] <= mid){
        dp[node][1]=-inf;
    }
    // cout<<mid<<"=> " _  node _ dp[node][0] _ dp[node][1]<<endl;
}
int check(int mid){
    alst.clear();
    for(int i=0;i<=sze;i++){
        dp[i][0]=inf;
        dp[i][1]=0;
    }

    dfs(1,0,mid);


    if(dp[1][0] + dp[1][1] > mid){
        alst.pb(1);
    }

    return alst.size();
}

void opt1z(){
    int n,k;
    cin>>n>>k;
    for(int i =1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        graph[u].pb({v,w});
        graph[v].pb({u,w});
    }
    int l =1;
    int r = (int)2e9 * (int)2e5;
    int ans=1;
    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid)<=k){
            ans = mid;
            r = mid -1;
        }
        else{
            l = mid+1;
        }
    }
    check(ans);
    set<int> a;
    for(auto v:alst){
        a.ins(v);
    }
    for(int i=1;i<=n;i++){
        if(a.size()<k && a.find(i)==a.end()){
            a.ins(i);
            // cout<< "new " _ i<<endl;
        }
    }
    cout<<ans<<"\n";
    for(auto v:a) cout<<v<<" ";cout<<endl;
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(long long int, long long int, long long int)':
Main.cpp:18:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for(auto [a,b]:graph[node]){
      |              ^
Main.cpp: In function 'void opt1z()':
Main.cpp:83:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   83 |         if(a.size()<k && a.find(i)==a.end()){
      |            ~~~~~~~~^~
Main.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   89 |     for(auto v:a) cout<<v<<" ";cout<<endl;
      |     ^~~
Main.cpp:89:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   89 |     for(auto v:a) cout<<v<<" ";cout<<endl;
      |                                ^~~~
Main.cpp: In function 'long long int check(long long int)':
Main.cpp:41:17: warning: iteration 200023 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |         dp[i][0]=inf;
      |         ~~~~~~~~^~~~
Main.cpp:40:18: note: within this loop
   40 |     for(int i=0;i<=sze;i++){
      |                 ~^~~~~

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