Submission #1111660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111660		vako_p	Parkovi (COCI22_parkovi)	C++14	110 / 110	631 ms	110408 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,k,dis[mxN],dis1[mxN],d[mxN],cnt[mxN],mid;
vector<pair<ll,ll>> v[mxN];
vector<pair<ll,ll>> vv[mxN];
bool vis[mxN];

void dfs(ll at, ll par){
	for(auto it : v[at]){
		if(it.first == par) continue;
		dfs(it.first, at);
		dis[at] = max(dis[at], dis[it.first] + it.second);
	}
}

void dfs1(ll at, ll par){
	if(dis[at] <= mid){
		dis1[at] = dis[at];
		d[at] = mid;
		cnt[at] = 1;
		vis[at] = true;
		for(auto it : v[at]){
			if(it.first == par) continue;
		 	vis[it.first] = false;
		}
//		cout << "dis[at] <= mid" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
		return;
	}
	vv[at].clear();
	ll c = 1,dd = 0,dd1 = 0,dd2 = 0;
	bool ok = true; 
	for(auto it : v[at]){
		if(it.first == par) continue;
		dfs1(it.first, at);
	 	d[it.first] -= it.second;
	 	if(d[it.first] >= 0) ok = false;
	 	dis1[it.first] += it.second;
		c += cnt[it.first] - (dis1[it.first] <= mid);
		dd2 = max(dd2, dis1[it.first]);
		if(dis1[it.first] <= mid){
			vv[at].pb({dis1[it.first], it.first});
			dd1 = max(dd1, dis1[it.first]);
			vis[it.first] = false;
		}
		else dd = max(dd, d[it.first]);
	}
	if(ok){
		cnt[at] = c;
		d[at] = mid;
		dis1[at] = dd1;
		vis[at] = true;
//		cout << "did not reach node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
		return;
	}
	sort(vv[at].begin(), vv[at].end()); 
	for(auto it : vv[at]){
		if(dd < it.first){
			cnt[at] = c;
			d[at] = mid;
			dis1[at] = dd1;
			vis[at] = true;
//			cout << "did not work without node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
			return;
		}
	}
	cnt[at] = c - 1;
	d[at] = dd;
	dis1[at] = dd2;
//	cout << "worked without node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
} 

bool ok(){
	for(int i = 0; i <= n; i++){
		vis[i] = false;
		dis1[i] = d[i] = cnt[i] = 0;
	}
	dfs1(1, 1);
	return (cnt[1] <= k);
}

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n - 1; i++){
		ll a,b,w;
		cin >> a >> b >> w;
		v[a].pb({b, w});
		v[b].pb({a, w});
	}
	dfs(1, 1);
	ll l = -1, r = 1e16;
	while(r > l + 1){
		mid = l + (r - l) / 2;
		if(ok()) r = mid;
		else l = mid;
	}
//	r = 1135814621;
	cout << r << '\n';
	mid = r;
	ok();
	ll cc = k;
	for(int i = 1; i <= n; i++){
		if(vis[i]){
			cout << i << ' ';
			cc--;
			assert(cc >= 0);
		}
	}
	for(int i = 1; i <= n and cc > 0; i++){
		if(!vis[i]){
			cout << i << ' ';
			cc--;
		}
	}
	return 0;
}

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