Submission #855216

#	Time	Username	Problem	Language	Result	Execution time	Memory
855216		serifefedartar	Parkovi (COCI22_parkovi)	C++17	0 / 110	386 ms	39884 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll MAXN = 2e5 + 5;

int n, k, q;
vector<vector<pair<int,ll>>> graph;
vector<int> parks, ans_parks;
ll nearest[MAXN], longest[MAXN];

void dfs(int node, int parent) {
	for (auto u : graph[node]) {
		if (u.f == parent)
			continue;
		dfs(u.f, node);

		nearest[node] = min(nearest[node], nearest[u.f] + u.s);
		if (longest[u.f] + u.s <= q) // bir üste aktarabilme durumu
			longest[node] = max(longest[node], longest[u.f] + u.s);
		else {
			parks.push_back(u.f);
			nearest[node] = min(nearest[node], u.s);
		}
	}

	if (nearest[node] + longest[node] <= q)
		longest[node] = -1e15; 
}

bool check(int x) {
	for (int i = 0; i < MAXN; i++)
		nearest[i] = 1e15, longest[i] = 0;
	parks.clear();

	q = x;
	dfs(1, 1);
	if (longest[1] > x)
		parks.push_back(1);

	return (parks.size() <= k);
}

int main() {
	fast
	cin >> n >> k;

	graph = vector<vector<pair<int,ll>>>(n+1, vector<pair<int,ll>>());
	for (int i = 1; i < n; i++) {
		ll a, b, w;
		cin >> a >> b >> w;
		graph[a].push_back({b, w});
		graph[b].push_back({a, w});
	}

	ll L = 0;
	ll R = 1e15;
	ll ans = -1;
	while (R >= L) {
		ll mid = L + (R-L)/2;
		if (check(mid)) {
			R = mid - 1;
			ans = mid;
			ans_parks = parks;
		} else
			L = mid + 1;
	}
	
	cout << ans << "\n";
	set<int> st;
	for (auto u : ans_parks)
		st.insert(u);
	int rem = k - st.size();
	for (int i = 1; i <= n && rem; i++) {
		if (st.count(i) == 0) {
			st.insert(i);
			rem--;
		}
	}

	for (auto u : st)
		cout << u << " ";
	cout << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'bool check(int)':
Main.cpp:46:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |  return (parks.size() <= k);
      |          ~~~~~~~~~~~~~^~~~

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