Submission #556131

#	Time	Username	Problem	Language	Result	Execution time	Memory
556131		new_acc	Parkovi (COCI22_parkovi)	C++14	110 / 110	2199 ms	92608 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e15;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
struct st{
    int a;
    ll b,c;
};
int n,k;
vector<pair<int,int> >graf[N];
bool stw[N];
st dp[N];
void dfs(int v,int o,ll x){
    vi v1,v2,v3;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        dfs(u,v,x);
    }
    if(graf[v].size()==1 and v!=o){
        stw[v]=1;
        dp[v]={1,0,0};
        return;
    }
    ll mini=INFl,mini2=INFl;
    int g=0,g2=0;
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b==0 and dp[u].c+(ll)c>x and mini>=dp[u].b+(ll)c) mini=dp[u].b+(ll)c,g=u;
    }
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b!=0 and mini2>=dp[u].b+(ll)c) mini2=dp[u].b+(ll)c,g2=u;
    }
    st res1={0,mini2,0};
    if(mini2>x)res1.a=INFi;
    else{
        for(auto [u,c]:graf[v]){
            if(u==o) continue;
            if(u==g2){
                res1.a+=dp[u].a;
                continue;
            }
            if(dp[u].b==0 and dp[u].c+(ll)c+mini2<=x) res1.a--,v1.push_back(u);
            else res1.b=min(res1.b,dp[u].b+(ll)c);
            res1.a+=dp[u].a;
        }
    }
    st res3={0,mini,0};
    if(mini>x) res3.a=INFi;
    else{
        for(auto [u,c]:graf[v]){
            if(u==o) continue;
            if(u==g){
                res3.a+=dp[u].a;
                continue;
            }
            if(dp[u].b==0 and dp[u].c+(ll)c+mini<=x) res3.a--,v3.push_back(u);
            else res3.b=min(res3.b,dp[u].b+(ll)c);
            res3.a+=dp[u].a;
        }
    }
    if(res1.a==res3.a){
        if(res3.b<res1.b) swap(res3,res1),swap(v1,v3);
    }else{
        if(res3.a<res1.a) swap(res3,res1),swap(v1,v3);
    }
    st res2={1,0,0};
    for(auto [u,c]:graf[v]){
        if(u==o) continue;
        if(dp[u].b==0 and dp[u].c+(ll)c<=x) res2.a--,res2.c=max(res2.c,(ll)c+dp[u].c),v2.push_back(u);
        res2.a+=dp[u].a;
    }
    if(res2.a<=res1.a){
        dp[v]=res2;
        stw[v]=1;
        for(auto u:v2) stw[u]=0;
    }else{
        dp[v]=res1;
        for(auto u:v1) stw[u]=0;
    }
}
bool check(ll x){
    for(int i=1;i<=n;i++) stw[i]=0;
    dfs(1,1,x);
    return dp[1].a<=k;
}
ll bs(ll pocz,ll kon){
    ll res,sr;
    while(pocz<=kon){
        sr=(pocz+kon)>>1LL;
        if(check(sr)) res=sr,kon=sr-1;
        else pocz=sr+1;
    }
    return res;
}
void solve(){
    cin>>n>>k;
    for(int a,b,c,i=1;i<n;i++){
        cin>>a>>b>>c;
        graf[a].push_back({b,c}),graf[b].push_back({a,c});
    }
    if(n==1){
        cout<<0<<"\n";
        return;
    }
    ll res=bs(0,(ll)1e15);
    check(res);
    cout<<res<<"\n";
    vi ans;
    for(int i=1;i<=n;i++) if(stw[i]) ans.push_back(i);
    for(int i=1;i<=n;i++) if(!stw[i] and ans.size()<k) ans.push_back(i);
    sort(ans.begin(),ans.end());
    for(auto u:ans) cout<<u<<" ";
    cout<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int, ll)':
Main.cpp:30:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp:52:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for(auto [u,c]:graf[v]){
      |                  ^
Main.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |         for(auto [u,c]:graf[v]){
      |                  ^
Main.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     for(auto [u,c]:graf[v]){
      |              ^
Main.cpp: In function 'void solve()':
Main.cpp:126:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  126 |     for(int i=1;i<=n;i++) if(!stw[i] and ans.size()<k) ans.push_back(i);
      |                                          ~~~~~~~~~~^~
Main.cpp: In function 'll bs(ll, ll)':
Main.cpp:109:12: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |     return res;
      |            ^~~

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