oj.uz

Submission #865260

# Submission time Handle Problem Language Result Execution time Memory
865260 2023-10-24T06:54:36 Z TAhmed33 Parkovi (COCI22_parkovi) C++
10 / 110
 2037 ms 78816 KB 
#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) {
	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 (good.empty() && bad.empty()) {
		cnt++; add(pos); return {0, 1};
	}
	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 = 3; 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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 74440 KB Output is correct
2 Correct 1006 ms 77656 KB Output is correct
3 Correct 1483 ms 43128 KB Output is correct
4 Correct 1465 ms 42092 KB Output is correct
5 Correct 1610 ms 41096 KB Output is correct
6 Correct 1396 ms 41112 KB Output is correct
7 Correct 1663 ms 39988 KB Output is correct
8 Correct 1891 ms 41656 KB Output is correct
9 Correct 1554 ms 41500 KB Output is correct
10 Correct 1897 ms 42312 KB Output is correct
11 Correct 1944 ms 45272 KB Output is correct
12 Correct 1926 ms 45376 KB Output is correct
13 Correct 2037 ms 48648 KB Output is correct
14 Correct 1658 ms 43792 KB Output is correct
15 Correct 1642 ms 42580 KB Output is correct
16 Correct 1711 ms 45092 KB Output is correct
17 Correct 1603 ms 43300 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

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