Submission #528947

#	Time	Username	Problem	Language	Result	Execution time	Memory
528947		penguinhacker	Parkovi (COCI22_parkovi)	C++14	110 / 110	1330 ms	34256 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, k;
vector<ar<int, 2>> adj[mxN];

ll lim, need[mxN], extra[mxN];
bool used[mxN];

void dfs(int u=0, int p=-1) {
	need[u]=0, extra[u]=-1;
	for (ar<int, 2> v : adj[u]) {
		if (v[0]==p)
			continue;
		dfs(v[0], u);
		if (extra[v[0]]!=-1) {
			if (extra[v[0]]>=v[1])
				extra[u]=max(extra[u], extra[v[0]]-v[1]);
		} else {
			if (need[v[0]]+v[1]>lim) {
				used[v[0]]=1;
				extra[v[0]]=lim;
				if (lim>=v[1])
					extra[u]=max(extra[u], lim-v[1]);
			} else
				need[u]=max(need[u], need[v[0]]+v[1]);
		}
	}
	if (extra[u]>=need[u])
		need[u]=0;
	else
		extra[u]=-1;
	if (u==0&&extra[u]==-1)
		used[u]=1;
}

bool ok(ll x) {
	lim=x;
	memset(used, 0, n);
	dfs();
	return count(used, used+n, 1)<=k;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	ll lb=0, rb=0;
	for (int i=1; i<n; ++i) {
		int u, v, w;
		cin >> u >> v >> w, --u, --v;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		rb+=w;
	}
	while(lb<rb) {
		ll mid=(lb+rb)/2;
		if (ok(mid))
			rb=mid;
		else
			lb=mid+1;
	}
	assert(ok(lb));
	k-=count(used, used+n, 1);
	for (int i=0; i<n&&k; ++i)
		if (!used[i])
			used[i]=1, --k;
	cout << lb << "\n";
	for (int i=0; i<n; ++i)
		if (used[i])
			cout << i+1 << " ";
	return 0;
}

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