Submission #865286

#	Time	Username	Problem	Language	Result	Execution time	Memory
865286		TAhmed33	Parkovi (COCI22_parkovi)	C++98	10 / 110	1753 ms	157328 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 25;
vector <pair <int, ll>> adj2[MAXN];
vector <pair <int, ll>> adj[MAXN];
ll mid;
int n, k;
bool vis[MAXN];
int cnt = 0;
vector <int> u, ans_vec;
void add (int pos) {
	//cout << "LOL: " << pos << '\n';
	u.push_back(pos);
}
pair <ll, ll> dfs (int pos, int par = -1) {
	vis[pos] = 1;
	if (par != -1 && adj[pos].size() == 1) return {0, 0};
	if (par == -1 && adj[pos].empty()) {
		cnt++; add(pos); return {0, 0};
	}
	vector <pair <ll, ll>> good, bad;
	int flag = 0;
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		auto k = dfs(j.first, pos);
		if (k.second == 0) {
			if (k.first + j.second > mid) {
				flag++; add(j.first); good.push_back({j.second, 1});
			} else bad.push_back({k.first + j.second, 0});
		} else {
			if (k.first + j.second > mid) continue;
			good.push_back({k.first + j.second, 1});		
		}
	}
	cnt += flag;
	sort(good.begin(), good.end());
	sort(bad.begin(), bad.end());
	/*
	cout << pos << " : \n";
	for (auto j : good) cout << j.first << " " << j.second << " | ";
	cout << '\n';
	for (auto j : bad) cout << j.first << " " << j.second << " | ";
	cout << '\n' << '\n';
	*/
	if (par == -1 && good.empty() && bad.empty()) {
		cnt++; add(pos); return {0, 1};
	}
	if (good.empty() && bad.empty()) {
		return {0, 0};
	}
	if (par == -1) {
		if (bad.empty()) return {0, 0};
		if (good.empty()) {
			cnt++; add(pos); return {0, 0};
		}
		if (bad.back().first + good.front().first > mid) {
			cnt++; add(pos); return bad.back();
		}
		return good.front();	
	}
	if (bad.empty()) {
		return good.front();
	}
	if (good.empty()) return bad.back();
	if (bad.back().first + good.front().first > mid) return bad.back();
	return good.front();
}
bool check () { 
	cnt = 0; u.clear();
	for (int i = 1; i <= n; i++) {
		vis[i] = 0; adj[i].clear();
		for (auto j : adj2[i]) {
			if (j.second <= mid) {
				adj[i].push_back(j);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i);
			//cout << i << " L L L L " << cnt << '\n';
		}
	}
	//cout << mid << " " << cnt << '\n';
	return cnt <= k;
}
int main () {
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj2[a].push_back({b, c});
		adj2[b].push_back({a, c});
	}
	//mid = 47; cout << check() << '\n'; return 0;
	ll l = 0, r = 1e16; ll ans = 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check()) {
			ans_vec = u;
			r = mid - 1; ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << '\n'; 
	set <int> pp; for (int i = 1; i <= n; i++) pp.insert(i);
	for (auto i : ans_vec) {
		cout << i << " "; pp.erase(i); k--;
	}
	while (k--) {
		cout << *(--pp.end()) << " "; pp.erase(pp.end());
	}
	cout << '\n';
}

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