Submission #1071142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071142		qqspeed20015	Parkovi (COCI22_parkovi)	C++14	110 / 110	434 ms	35592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 3;
const long long INF = 1e18;
 
int n, k;
vector<pair <int, int>> adj[N];
 
int num_park = 0;
bool is_park[N];
long long near[N], reach[N];
 
void input() {
	cin >> n >> k;
 
	for(int i = 1; i < n; i++) {
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}
}
 
void dfs(int u, int p, long long limit) {
	near[u] = INF; reach[u] = 0;
 
	for (int i = 0; i < (int) adj[u].size(); i++) {
		int v = adj[u][i].first, w = adj[u][i].second;
 
		if (v != p) {
			dfs(v, u, limit);
 
			if (reach[v] + min(1LL * w, near[v]) <= limit) {
				near[u] = min(near[u], near[v] + w);
				if(reach[v] + near[v] > limit) reach[u] = max(reach[u], reach[v] + w);
			} else {
				num_park++;
				is_park[v] = true;
				near[u] = min(near[u], 1LL * w);
			}
		}	
	}
}
 
bool check(long long limit) {
	num_park = 0;
	for(int i = 1; i <= n; i++) is_park[i] = false;
 
	dfs(1, -1, limit);
 
	if (reach[1] + near[1] > limit) {
		num_park++;
		is_park[1] = true;
	}
 
	return (num_park <= k);
}
 
void process() {
	long long l = 0, r = 1e15, res = 0;
	while (l <= r) {
		long long m = (l + r) >> 1;
		if (check(m)) {
			res = m;
			r = m - 1;
		} else {
			l = m + 1;
		}
	}
 
	cout << res << endl;

	check(res);
	vector<int> nodes;
	for(int i = 1; i <= n; i++) if(is_park[i]) nodes.push_back(i);
	for(int i = 1; i <= n; i++) if((int)nodes.size() < k && !is_park[i]) nodes.push_back(i);
	for(int node : nodes) cout << node << " ";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    input();
    process();
 
    return 0;
}

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