oj.uz

Submission #865288

# Submission time Handle Problem Language Result Execution time Memory
865288 2023-10-24T07:07:11 Z TAhmed33 Parkovi (COCI22_parkovi) C++
10 / 110
 2407 ms 166056 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("trapv")
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'; //return 0;
	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 2 ms 9816 KB Output is correct
2 Runtime error 9 ms 19548 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 1243 ms 77412 KB Output is correct
2 Correct 1350 ms 79316 KB Output is correct
3 Correct 1826 ms 38428 KB Output is correct
4 Correct 2067 ms 37972 KB Output is correct
5 Correct 1936 ms 37064 KB Output is correct
6 Correct 1959 ms 37080 KB Output is correct
7 Correct 1992 ms 37256 KB Output is correct
8 Correct 2103 ms 38744 KB Output is correct
9 Correct 2037 ms 38224 KB Output is correct
10 Correct 2117 ms 38920 KB Output is correct
11 Correct 2304 ms 41808 KB Output is correct
12 Correct 2258 ms 42072 KB Output is correct
13 Correct 2407 ms 45036 KB Output is correct
14 Correct 2070 ms 41632 KB Output is correct
15 Correct 2107 ms 40580 KB Output is correct
16 Correct 2248 ms 42148 KB Output is correct
17 Correct 2099 ms 40396 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1398 ms 80344 KB Output is correct
2 Correct 1341 ms 78628 KB Output is correct
3 Correct 1287 ms 75068 KB Output is correct
4 Correct 1288 ms 75084 KB Output is correct
5 Correct 860 ms 80212 KB Output is correct
6 Correct 1065 ms 79660 KB Output is correct
7 Correct 1146 ms 81976 KB Output is correct
8 Correct 1388 ms 81236 KB Output is correct
9 Correct 1384 ms 80184 KB Output is correct
10 Correct 1286 ms 78956 KB Output is correct
11 Correct 1265 ms 76220 KB Output is correct
12 Runtime error 1136 ms 166056 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 2 ms 9816 KB Output is correct
2 Runtime error 9 ms 19548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -