Submission #930454

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930454	2024-02-19T19:45:43 Z	NK_	Parkovi (COCI22_parkovi)	C++17	110 / 110	887 ms	50636 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	287 ms	37760 KB	Output is correct
2	Correct	315 ms	40016 KB	Output is correct
3	Correct	178 ms	20004 KB	Output is correct
4	Correct	527 ms	19432 KB	Output is correct
5	Correct	528 ms	18512 KB	Output is correct
6	Correct	476 ms	18768 KB	Output is correct
7	Correct	699 ms	17604 KB	Output is correct
8	Correct	638 ms	18524 KB	Output is correct
9	Correct	674 ms	18768 KB	Output is correct
10	Correct	615 ms	19208 KB	Output is correct
11	Correct	469 ms	21512 KB	Output is correct
12	Correct	442 ms	21076 KB	Output is correct
13	Correct	574 ms	22992 KB	Output is correct
14	Correct	520 ms	19716 KB	Output is correct
15	Correct	471 ms	19156 KB	Output is correct
16	Correct	568 ms	20808 KB	Output is correct
17	Correct	424 ms	19792 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	40880 KB	Output is correct
2	Correct	317 ms	39764 KB	Output is correct
3	Correct	270 ms	37724 KB	Output is correct
4	Correct	278 ms	37716 KB	Output is correct
5	Correct	333 ms	49608 KB	Output is correct
6	Correct	362 ms	44716 KB	Output is correct
7	Correct	420 ms	46964 KB	Output is correct
8	Correct	298 ms	40276 KB	Output is correct
9	Correct	309 ms	40272 KB	Output is correct
10	Correct	294 ms	39308 KB	Output is correct
11	Correct	266 ms	38040 KB	Output is correct
12	Correct	410 ms	50636 KB	Output is correct
13	Correct	360 ms	48396 KB	Output is correct
14	Correct	360 ms	44740 KB	Output is correct
15	Correct	284 ms	38484 KB	Output is correct
16	Correct	281 ms	36964 KB	Output is correct
17	Correct	317 ms	36832 KB	Output is correct
18	Correct	318 ms	38740 KB	Output is correct
19	Correct	313 ms	46788 KB	Output is correct
20	Correct	326 ms	45512 KB	Output is correct
21	Correct	314 ms	43172 KB	Output is correct

Subtask #4

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	460 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	456 KB	Output is correct
15	Correct	287 ms	37760 KB	Output is correct
16	Correct	315 ms	40016 KB	Output is correct
17	Correct	178 ms	20004 KB	Output is correct
18	Correct	527 ms	19432 KB	Output is correct
19	Correct	528 ms	18512 KB	Output is correct
20	Correct	476 ms	18768 KB	Output is correct
21	Correct	699 ms	17604 KB	Output is correct
22	Correct	638 ms	18524 KB	Output is correct
23	Correct	674 ms	18768 KB	Output is correct
24	Correct	615 ms	19208 KB	Output is correct
25	Correct	469 ms	21512 KB	Output is correct
26	Correct	442 ms	21076 KB	Output is correct
27	Correct	574 ms	22992 KB	Output is correct
28	Correct	520 ms	19716 KB	Output is correct
29	Correct	471 ms	19156 KB	Output is correct
30	Correct	568 ms	20808 KB	Output is correct
31	Correct	424 ms	19792 KB	Output is correct
32	Correct	294 ms	40880 KB	Output is correct
33	Correct	317 ms	39764 KB	Output is correct
34	Correct	270 ms	37724 KB	Output is correct
35	Correct	278 ms	37716 KB	Output is correct
36	Correct	333 ms	49608 KB	Output is correct
37	Correct	362 ms	44716 KB	Output is correct
38	Correct	420 ms	46964 KB	Output is correct
39	Correct	298 ms	40276 KB	Output is correct
40	Correct	309 ms	40272 KB	Output is correct
41	Correct	294 ms	39308 KB	Output is correct
42	Correct	266 ms	38040 KB	Output is correct
43	Correct	410 ms	50636 KB	Output is correct
44	Correct	360 ms	48396 KB	Output is correct
45	Correct	360 ms	44740 KB	Output is correct
46	Correct	284 ms	38484 KB	Output is correct
47	Correct	281 ms	36964 KB	Output is correct
48	Correct	317 ms	36832 KB	Output is correct
49	Correct	318 ms	38740 KB	Output is correct
50	Correct	313 ms	46788 KB	Output is correct
51	Correct	326 ms	45512 KB	Output is correct
52	Correct	314 ms	43172 KB	Output is correct
53	Correct	632 ms	19280 KB	Output is correct
54	Correct	727 ms	19764 KB	Output is correct
55	Correct	667 ms	20716 KB	Output is correct
56	Correct	638 ms	20564 KB	Output is correct
57	Correct	794 ms	24220 KB	Output is correct
58	Correct	658 ms	19360 KB	Output is correct
59	Correct	756 ms	31180 KB	Output is correct
60	Correct	887 ms	19024 KB	Output is correct
61	Correct	617 ms	17420 KB	Output is correct
62	Correct	515 ms	22844 KB	Output is correct
63	Correct	752 ms	19184 KB	Output is correct
64	Correct	743 ms	28248 KB	Output is correct
65	Correct	802 ms	19344 KB	Output is correct
66	Correct	748 ms	23720 KB	Output is correct
67	Correct	512 ms	18256 KB	Output is correct
68	Correct	858 ms	30672 KB	Output is correct
69	Correct	349 ms	40016 KB	Output is correct
70	Correct	280 ms	37468 KB	Output is correct
71	Correct	382 ms	45524 KB	Output is correct
72	Correct	171 ms	19012 KB	Output is correct
73	Correct	160 ms	18820 KB	Output is correct
74	Correct	181 ms	23736 KB	Output is correct
75	Correct	521 ms	21980 KB	Output is correct
76	Correct	558 ms	21328 KB	Output is correct
77	Correct	531 ms	21072 KB	Output is correct
78	Correct	459 ms	22352 KB	Output is correct