Submission #696684

#	Time	Username	Problem	Language	Result	Execution time	Memory
696684		TranGiaHuy1508	Parkovi (COCI22_parkovi)	C++17	110 / 110	1358 ms	36376 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long
const int inf = 1e17;

int n, k, lim;
vector<vector<pair<int, int>>> adj;
vector<int> lst;

pair<int, int> dfs(int x, int p = -1, int wpar = 0){
	int maxw = 0, minb = inf;
	for (auto [y, w]: adj[x]){
		if (y == p) continue;
		auto sbt = dfs(y, x, w);
		maxw = max(maxw, sbt.first);
		minb = min(minb, sbt.second);
	}

	if (maxw + minb <= lim) return {0, minb + wpar};
	if (p != -1){
		if (maxw + wpar > lim){
			lst.push_back(x);
			return {0, wpar};
		}
	}
	else{
		lst.push_back(x);
		return {0, wpar};
	}
	return {maxw + wpar, minb + wpar};
}

bool check(int threshold){
	lst.clear();
	lim = threshold;
	dfs(0);
	return (int)lst.size() <= k;
}

void main_program(){
	cin >> n >> k;

	adj.resize(n);

	for (int i = 0; i < n-1; i++){
		int a, b, w; cin >> a >> b >> w;
		a--; b--;

		adj[a].emplace_back(b, w);
		adj[b].emplace_back(a, w);
	}

	int l = 0, r = 1e15;
	while (l < r){
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	check(l);
	cout << l << "\n";
	vector<int> mark(n);
	for (auto i: lst){
		mark[i] = 1; k--;
	}
	for (int i = 0; i < n; i++){
		if (!mark[i] && k){
			mark[i] = 1; k--;
		}
	}
	for (int i = 0; i < n; i++){
		if (mark[i]) cout << i+1 << " ";
	}
	cout << "\n";
}

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