Submission #869082

#	Time	Username	Problem	Language	Result	Execution time	Memory
869082		Mr_Ph	Parkovi (COCI22_parkovi)	C++14	110 / 110	1341 ms	51832 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)
{
    for(auto i:adj[node])
    {
		if (i.first == parent) continue;
			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(fpark[node]+cpark[node]<=mid){
	    fpark[node]=-1e15;
		return;
	}
	if (fpark[node]+prv>mid)
	{
		xd.push_back(node);
		curk++;
		fpark[node]=-1e15;
		cpark[node]=0;
	}
    else if(node==1&&fpark[node]>=0)
    {
        curk++;
        xd.push_back(node);
    }
}
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 l=1,r=1e15;
    int ans=0;
    vi ans1;
    vi lol;
    while(l<=r)
    {
        int mid=(l+r)/2;
        curk=0;
        xd=lol;
        for(int i=1; i<=n; i++)
            cpark[i]=1e15,fpark[i]=-1e15;
        dfs(1,0,mid,0);
        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();
}

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