Submission #545356

#	Time	Username	Problem	Language	Result	Execution time	Memory
545356		tibinyte	Parkovi (COCI22_parkovi)	C++14	0 / 110	3 ms	4948 KiB

Main

#include <bits/stdc++.h>
#define inf 1e16
using namespace std;
ifstream fin("geana.in");
ofstream fout("geana.out");
long long n, k;
vector<pair<long long, long long>> g[200001];
vector<int> sol;
long long deep[200001], closest[200001];
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 (closest[node] > lim && deep[node] < 0) {
		deep[node] = 0;
	}
	if (deep[node] + closest[node] <= lim) {
		deep[node] = -inf;
		return;
	}
	if (deep[node] + cost > lim || (node==1&&deep[node])) {
		if (reconst) {
			sol.push_back(node);
		}
		ans++;
		closest[node] = 0;
		deep[node] = -inf;
	}
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	fin >> n >> k;
	for (long long i = 2; i <= n; ++i) {
		long long a, b, w;
		fin >> 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;
		}
	}
	fout << 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) {
		fout << i << ' ';
	}
}

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