Submission #825996

#	Time	Username	Problem	Language	Result	Execution time	Memory
825996		fdnfksd	Parkovi (COCI22_parkovi)	C++14	110 / 110	1393 ms	35032 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define endl '\n'
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
using namespace std;
const int maxN=2e5+69;
const int mod=1e9+7;
ll n,k,dist[2][maxN];
vector<pll> adj[maxN];
bool take[maxN];
ll x,c;
void dfs(ll u,ll p=0){
    dist[1][u]=1e18;
    for(auto z:adj[u]){
        ll v=z.first;
        if(v==p)continue;
        ll w=z.second;
        dfs(v,u);
        if(dist[0][v]!=-1&&dist[0][v]+w>x)dist[1][v]=0,dist[1][u]=min(dist[1][u],w),dist[0][v]=-1,c++,take[v]=1;
        else {
            if(dist[0][v]!=-1)dist[0][u]=max(dist[0][u],dist[0][v]+w);
            dist[1][u]=min(dist[1][u],dist[1][v]+w);
        }
    }
    if(dist[0][u]+dist[1][u]<=x)dist[0][u]=-1;
    if(u==1&&dist[0][1]!=-1)c++,take[1]=1;
}
bool check(){
    c=0;
    memset(take,0,sizeof take);
    memset(dist,0,sizeof dist);
    dfs(1);
    return c<=k;
}
void Enter(){
    cin>>n>>k;
    for(int i=1;i<n;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    ll l=0,r=2e14+69;
    while(l<r){
        x=l+r>>1;
        if(!check())l=x+1;
        else r=x;
    }
    x=l;
    check();
    cout<<l<<endl;
    for(int i=1;i<=n&&c<k;i++)if(!take[i])take[i]=1,c++;
    for(int i=1;i<=n;i++)if(take[i])cout<<i<<' ';
}
//amogus
signed main(){
    open("KTREE");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //int t=1;cin>>t;while(t--)
    Enter();
}

Compilation message (stderr)

Main.cpp: In function 'void Enter()':
Main.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         x=l+r>>1;
      |           ~^~
Main.cpp: In function 'int main()':
Main.cpp:7:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:5: note: in expansion of macro 'open'
   60 |     open("KTREE");
      |     ^~~~
Main.cpp:7:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:5: note: in expansion of macro 'open'
   60 |     open("KTREE");
      |     ^~~~

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