Submission #930454

#	Time	Username	Problem	Language	Result	Execution time	Memory
930454		NK_	Parkovi (COCI22_parkovi)	C++17	110 / 110	887 ms	50636 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using pl = pair<ll, ll>;
using vi = V<int>;
using vpl = V<pl>;
using vl = V<ll>;

const ll INFL = 1e18;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K; cin >> N >> K;

	V<vpl> adj(N); vi d(N); for(int i = 0; i < N - 1; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	vi ans;
	auto check = [&](ll k) {

		ans = {};
		function<pl(int, int, ll)> dfs = [&](int u, int p, ll d) {
			ll close = -INFL, far = 0;
			for(auto& e : adj[u]) {
				int v; ll w; tie(v, w) = e; if (v == p) continue;
				pl R = dfs(v, u, w);
				if (R.f) close = max(close, R.s);
				else far = max(far, R.s);
			}

			pl R;
			if (close >= far) R = mp(1, close - d);
			else R = mp(0, far + d);
			
			if (R.f && R.s < 0) R = mp(0, 0);
			if (!R.f && R.s > k) {
				ans.pb(u); R = mp(1, k - d);
			}

			return R;
		};

		dfs(0, -1, INFL);

		return sz(ans) <= K;
	};

	ll lo = 0, hi = ll(3e15);
	while(lo < hi) {
		ll mid = (lo + hi) / 2;
		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}

	check(lo);

	set<int> in(begin(ans), end(ans));

	int cur = 0;
	while(sz(ans) < K) {
		if (!in.count(cur)) ans.pb(cur);
		cur++;
	}

	cout << lo << nl;
	for(auto& x : ans) cout << x + 1 << " ";
	cout << nl;

	exit(0-0);
}

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