Submission #526743

#	Time	Username	Problem	Language	Result	Execution time	Memory
526743		siewjh	Parkovi (COCI22_parkovi)	C++17	110 / 110	1184 ms	43000 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int MAXN = 200'005;
const ll inf = 1e16;
vector<pair<int, ll>> adjlist[MAXN];
vector<int> ans;
pair<bool, ll> dfs(int x, int par, ll dist, ll maxdist) {
	ll over = -inf, under = 0;
	for (auto nxt : adjlist[x]) {
		int nn = nxt.first; ll nd = nxt.second;
		if (nn == par) continue;
		auto res = dfs(nn, x, nd, maxdist);
		if (res.first) over = max(over, res.second);
		else under = max(under, res.second);
	}
	if (over >= under) return { 1, over - dist };
	else if (under + dist <= maxdist) return { 0, under + dist };
	ans.push_back(x);
	return { 1, maxdist - dist };
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nums, parks; cin >> nums >> parks;
	for (int i = 0; i < nums - 1; i++) {
		int a, b; ll w; cin >> a >> b >> w;
		adjlist[a].push_back({ b, w });
		adjlist[b].push_back({ a, w });
	}
	ll l = 0, r = inf, opt;
	while (l <= r) {
		ll m = (l + r) >> 1;
		if (m == 8) {
			cout << "";
		}
		dfs(1, -1, inf, m);
		if (ans.size() <= parks) {
			opt = m;
			r = m - 1;
		}
		else l = m + 1;
		ans.clear();
	}
	cout << opt << '\n';
	dfs(1, -1, inf, opt);
	set<int> s;
	for (auto x : ans) s.insert(x);
	for (int i = 1; ans.size() < parks; i++)
		if (!s.count(i))
			ans.push_back(i);
	for (auto x : ans) cout << x << ' ';
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:41:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |   if (ans.size() <= parks) {
      |       ~~~~~~~~~~~^~~~~~~~
Main.cpp:52:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |  for (int i = 1; ans.size() < parks; i++)
      |                  ~~~~~~~~~~~^~~~~~~
Main.cpp:49:21: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |  dfs(1, -1, inf, opt);
      |                     ^

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