Submission #1159170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159170		kerem	Parkovi (COCI22_parkovi)	C++20	110 / 110	491 ms	35128 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 200000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(0)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;


int n,k;
vector<int> ans;
vector<pii> v[N+5];

pii dfs(int x,int ata,int dist){
	pii t={inf,0};
	int pw=0;
	for(auto [i,w]:v[x]){
		if(i==ata){
			pw=w;
			continue;
		}
		pii p=dfs(i,x,dist);
		t.fr=min(t.fr,p.fr+w);
		t.sc=max(t.sc,p.sc+w);
	}
	if(t.sc+t.fr<=dist)
		t.sc=-pw;
	if(t.sc+pw>dist){
		ans.pb(x);
		t={0,-pw};
	}
	return t;
}
void solve(){
	cin >> n >> k;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin >> x >> y >> z;
		v[x].pb({y,z});
		v[y].pb({x,z});
	}
	int l=0,r=inf;
	while(l<r){
		int mid=(l+r)/2;
		ans.clear();
		pii p=dfs(1,0,mid);
		if(p.fr+p.sc>mid) ans.pb(1);
		//~ cout << l sp mid sp r sp ans.size() << endl;
		if((int)ans.size()>k) l=mid+1;
		else r=mid;
	}
	cout << l << endl;
	ans.clear();
	pii p=dfs(1,0,l);
	if(p.fr+p.sc>l) ans.pb(1);
	
	sort(all(ans));
	int j=0;
	for(int i=1;i<=n && (int)ans.size()<k;i++){
		if(i==ans[j]) j++;
		else ans.pb(i);
	}
	for(auto i:ans)
		cout << i << " ";
}     
int32_t main(){
	//~ freopen("cbarn.in","r",stdin);
	//~ freopen("cbarn.out","w",stdout);
	fast;
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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