oj.uz

Submission #865286

# Submission time Handle Problem Language Result Execution time Memory
865286 2023-10-24T07:04:37 Z TAhmed33 Parkovi (COCI22_parkovi) C++
10 / 110
 1753 ms 157328 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) {
	//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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Runtime error 9 ms 19556 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 73296 KB Output is correct
2 Correct 1008 ms 75656 KB Output is correct
3 Correct 1452 ms 41748 KB Output is correct
4 Correct 1455 ms 40320 KB Output is correct
5 Correct 1321 ms 39508 KB Output is correct
6 Correct 1340 ms 39580 KB Output is correct
7 Correct 1329 ms 38760 KB Output is correct
8 Correct 1414 ms 40536 KB Output is correct
9 Correct 1381 ms 40156 KB Output is correct
10 Correct 1457 ms 40736 KB Output is correct
11 Correct 1605 ms 43360 KB Output is correct
12 Correct 1586 ms 43644 KB Output is correct
13 Correct 1753 ms 46792 KB Output is correct
14 Correct 1480 ms 42376 KB Output is correct
15 Correct 1473 ms 41520 KB Output is correct
16 Correct 1582 ms 43520 KB Output is correct
17 Correct 1490 ms 41936 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 76912 KB Output is correct
2 Correct 1030 ms 77136 KB Output is correct
3 Correct 995 ms 73476 KB Output is correct
4 Correct 977 ms 73552 KB Output is correct
5 Correct 652 ms 78508 KB Output is correct
6 Correct 773 ms 78012 KB Output is correct
7 Correct 776 ms 80288 KB Output is correct
8 Correct 1016 ms 78676 KB Output is correct
9 Correct 1084 ms 77904 KB Output is correct
10 Correct 987 ms 76624 KB Output is correct
11 Correct 984 ms 74068 KB Output is correct
12 Runtime error 837 ms 157328 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9820 KB Output is correct
2 Runtime error 9 ms 19556 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -