Submission #869004

#	Time	Username	Problem	Language	Result	Execution time	Memory
869004		Mr_Ph	Parkovi (COCI22_parkovi)	C++14	0 / 110	342 ms	49148 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long long int lli;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
ll mod=(ll)1e9+7;
ll mod1=998244353;
///the defines :)
#define endl '\n'
#define vi vector<int>
#define vll vector<ll>
#define ent(arr) for(int i=0;i<arr.size();i++)cin>>arr[i];
#define all(arr) arr.begin(),arr.end()
#define allr(arr) arr.rbegin(),arr.rend()
#define sz size()
#define int long long
vector<vector<pair<int,int>>>adj;
vector<int>cpark;
vector<int>fpark;
int curk;
vi xd;
void dfs(int node,int parent,int mid,int prv)
{
    int cnt=0;
    for(auto i:adj[node])
    {
        if(i.first==parent)continue;
        cnt++;
        dfs(i.first,node,mid,i.second);
        cpark[node]=min(cpark[node],cpark[i.first]+i.second);
        fpark[node]=max(fpark[node],fpark[i.first]+i.second);
    }
    if(cpark[node]>mid)
        fpark[node]=max(0ll,fpark[node]);
    if(cpark[node]+fpark[node]<=mid)
    {
        fpark[node]=-1e15;
        return;
    }
    if(fpark[node]+prv>mid)
    {
        curk++;
        xd.push_back(node);
        fpark[node]=-1e15;
        cpark[node]=0;
    }
}
void preprocess() {}
void solve()
{
    int n,k;
    cin>>n>>k;
    adj.resize(n+1);
    cpark.resize(n+1);
    fpark.resize(n+1);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    int leaf=0;
    for(int i=1; i<=n; i++)
        if(adj[i].sz==1)
            leaf=i;
    int l=1,r=1e15;
    int ans=0;
    vi ans1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        curk=0;
        xd.clear();
        for(int i=1; i<=n; i++)
            cpark[i]=1e15,fpark[i]=-1e15;
        dfs(1,0,mid,0);
      //  cout<<endl;
        if(fpark[1]>0&&(!xd.sz||xd[xd.sz-1]!=1))
        {
            xd.push_back(1);
            curk++;
        }
        if(curk<=k)
        {
            ans=mid;
            ans1=xd;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<ans<<endl;
    map<int,int>mp;
    for(auto i:ans1)
    {
        mp[i]++;
        cout<<i<<" ";
    }
    int cnt=ans1.sz;
    for(int i=1; i<=n; i++)
    {
        if(!mp[i]&&cnt<k)
        {
            cnt++;
            cout<<i<<" ";
        }
    }
    cout<<endl;
}
signed main()
{
    // freopen("meta_game_input.txt","r",stdin);
    // freopen("otput.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    preprocess();
    //bla();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:69:9: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
   69 |     int leaf=0;
      |         ^~~~

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