oj.uz

Submission #855216

# Submission time Handle Problem Language Result Execution time Memory
855216 2023-09-30T20:38:39 Z serifefedartar Parkovi (COCI22_parkovi) C++17
0 / 110
 386 ms 39884 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 386 ms 38480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 39884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3416 KB Output isn't correct
2 Halted 0 ms 0 KB -