Submission #1167501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167501		sleepntsheep	Parkovi (COCI22_parkovi)	C++20	110 / 110	698 ms	44308 KiB

Main

#include <cstdio>
#include <vector>
#include <utility>

#define N 330033

int dbg,n, k, miku[N], skbd, mikuized[N];
std::vector<std::pair<int, int> > g[N];
long long mid;


std::pair<long long, long long> dfs(int u, int p) {
	long long down = 1e17, farfar = -1e17;

	std::vector<std::pair<long long, long long>> br;
	for (auto [w, v] : g[u]) {
		if (v == p) continue;
		auto xy = dfs(v, u);
		xy.first += w;

		if (xy.first > mid) {
			xy.first = -1e17;
			xy.second = 0;
			miku[skbd++] = v;
		}
		if (down > xy.second + w)
			down = xy.second + w;
		br.push_back(xy);
	}

	for (auto xy: br) {
		if (xy.first + down <= mid) {
			xy.first = 0;
		}
		else
			farfar = std::max(farfar, xy.first);
	}
	if (down > mid)
		farfar = std::max(farfar, 0ll);

	return {farfar, down};
}

int check() {
	skbd = 0;
	auto xy = dfs(1, 1);
	if (xy.first >= 0)
		miku[skbd++] = 1;
	return skbd <= k;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int u, v, w, i = 1; i < n; ++i) {
		scanf("%d%d%d", &u, &v, &w);
		g[u].emplace_back(w, v);
		g[v].emplace_back(w, u);
	}


	long long lower = -1 , upper = 3e14;

	while (upper - lower > 1) {
		mid = lower + (upper - lower) / 2;
		if (check()) upper = mid;
		else lower = mid;
	}

	mid = upper;
	check();

	printf("%lld\n", upper);

	for (int i = 0; i < skbd; ++i)
		printf("%d ", miku[i]), mikuized[miku[i]] = 1;

	for (int i = 1; skbd < k && i <= n; ++i) {
		if (! mikuized[i]) {
			printf("%d ", i);
			++skbd;
		}
	}

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d%d", &n, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 scanf("%d%d%d", &u, &v, &w);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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