oj.uz

Submission #545357

# Submission time Handle Problem Language Result Execution time Memory
545357 2022-04-04T10:49:11 Z tibinyte Parkovi (COCI22_parkovi) C++14
0 / 110
 444 ms 38708 KB 
#include <bits/stdc++.h>
#define inf 1e16
using namespace std;
ifstream fin("geana.in");
ofstream fout("geana.out");
long long n, k;
vector<pair<long long, long long>> g[200001];
vector<int> sol;
long long deep[200001], closest[200001];
long long ans;
void dfs(long long node, long long parent, long long lim, long long cost, bool reconst) {
	closest[node] = inf;
	deep[node] = -inf;
	for (auto i : g[node]) {
		if (i.first != parent) {
			dfs(i.first, node, lim, i.second, reconst);
			deep[node] = max(deep[node], deep[i.first] + i.second);
			closest[node] = min(closest[node], closest[i.first] + i.second);
		}
	}
	if (closest[node] > lim && deep[node] < 0) {
		deep[node] = 0;
	}
	if (deep[node] + closest[node] <= lim) {
		deep[node] = -inf;
		return;
	}
	if (deep[node] + cost > lim || (node==1&&deep[node])) {
		if (reconst) {
			sol.push_back(node);
		}
		ans++;
		closest[node] = 0;
		deep[node] = -inf;
	}
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> k;
	for (long long i = 2; i <= n; ++i) {
		long long a, b, w;
		cin >> a >> b >> w;
		g[a].push_back({ b,w });
		g[b].push_back({ a,w });
	}
	long long st = 0, dr = inf;
	long long rep = 0;
	while (st <= dr) {
		long long mid = (st + dr) / 2;
		ans = 0;
		dfs(1, 0, mid, 0, 0);
		if (ans <= k) {
			rep = mid;
			dr = mid - 1;
		}
		else {
			st = mid + 1;
		}
	}
	cout << rep << '\n';
	dfs(1, 0, rep, 0, true);
	vector<bool> seen(n + 1);
	for (auto i : sol) {
		seen[i] = true;
	}
	for (int i = 1; i <= n; ++i) {
		if ((int)sol.size() == k) {
			break;
		}
		if (!seen[i]) {
			sol.push_back(i);
		}
	}
	for (auto i : sol) {
		cout << i << ' ';
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5040 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 3 ms 5040 KB Output isn't correct
3 Halted 0 ms 0 KB -