Submission #930455

#	Time	Username	Problem	Language	Result	Execution time	Memory
930455		NK_	Parkovi (COCI22_parkovi)	C++17	110 / 110	921 ms	47116 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; ll k = -1;
	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;
	};

	ll lo = 0, hi = ll(3e15);
	while(lo < hi) {
		ll mid = (lo + hi) / 2;
		ans = {}; k = mid;
		dfs(0, -1, INFL);
		if (sz(ans) <= K) hi = mid;
		else lo = mid + 1;
	}

	ans = {}; k = lo;
	dfs(0, -1, INFL);

	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