Submission #545341

#	Time	Username	Problem	Language	Result	Execution time	Memory
545341		tibinyte	Parkovi (COCI22_parkovi)	C++14	0 / 110	48 ms	14744 KiB

Main

#include <bits/stdc++.h>
#define inf 1e16
using namespace std;
long long n, k;
vector<pair<long long,long long>> g[100001];
vector<int> sol;
long long deep[100001], closest[100001];
long long ans;
void dfs(long long node, long long parent, long long lim, long long cost, bool reconst) {
	closest[node] = inf;
	deep[node] = -inf;
	for (auto i : g[node]) {
		if (i.first != parent) {
			dfs(i.first, node, lim, i.second, reconst);
			deep[node] = max(deep[node], deep[i.first] + i.second);
			closest[node] = min(closest[node], closest[i.first] + i.second);
		}
	}
	if (deep[node] < 0 && closest[node] > lim) {
		deep[node] = 0;
	}
	if (deep[node] + closest[node] <= lim) {
		deep[node] = -inf;
		return;
	}
	if (deep[node] + cost > lim) {
		if (reconst) {
			sol.push_back(node);
		}
		ans++;
		closest[node] = 0;
		deep[node] = -inf;
	}
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> k;
	for (long long i = 2; i <= n; ++i) {
		long long a, b,w;
		cin >> a >> b>>w;
		g[a].push_back({ b,w });
		g[b].push_back({ a,w });
	}
	long long st = 0, dr = inf;
	long long rep = 0;
	while (st <= dr) {
		long long mid = (st + dr) / 2;
		ans = 0;
		dfs(1, 0, mid, 0, 0);
		if (ans <= k) {
			rep = mid;
			dr = mid - 1;
		}
		else {
			st = mid + 1;
		}
	}
	cout << rep << '\n';
	dfs(1, 0, rep, 0, true);
	vector<bool> seen(n + 1);
	for (auto i : sol) {
		seen[i] = true;
	}
	for (int i = 1; i <= n; ++i) {
		if ((int)sol.size() == k) {
			break;
		}
		if (!seen[i]) {
			sol.push_back(i);
		}
	}
	for (auto i : sol) {
		cout << i << ' ';
	}
}

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