oj.uz

Submission #526756

# Submission time Handle Problem Language Result Execution time Memory
526756 2022-02-16T04:03:12 Z hmm789 Parkovi (COCI22_parkovi) C++14
0 / 110
 391 ms 31336 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 

vector<pair<int, int>> adj[200000];

vector<int> vec;

pair<int, int> dp(int x, int v, int par) {
	int mxover = -1e18, mxunder = 0, pard;
	for(auto i : adj[x]) {
		if(i.first == par) {
			pard = i.second;
			continue;
		}
		pair<int, int> tmp = dp(i.first, v, x);
		if(tmp.first == -1) mxunder = max(mxunder, tmp.second);
		else mxover = max(mxover, tmp.second);
	}
	pair<int, int> res;
	if(mxover >= mxunder) {
		res = make_pair(1, mxover-pard);
	} else {
		res = make_pair(-1, mxunder + pard);
	}
	if(res.first == -1 && res.second > v) {
		vec.push_back(x);
		res = make_pair(1, v-pard);
	}
	if(res.first == 1 && res.second < 0) {
		res = make_pair(-1, 0);
	}
	return res;
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k, x, y, w;
	cin >> n >> k;
	for(int i = 0; i < n-1; i++) {
		cin >> x >> y >> w;
		x--; y--;
		adj[x].push_back(make_pair(y, w));
		adj[y].push_back(make_pair(x, w));
	}
	int l = 0, r = 1e18, m;
	while(l < r) {
		m = (l+r)/2;
		vec.clear();
		dp(0, m, 2e18);
		if(vec.size() > k) l = m+1;
		else r = m;
	}
	vec.clear();
	dp(0, l, 2e18);
	cout << l << '\n';
	sort(vec.begin(), vec.end());
	for(int i : vec) cout << i+1 << " ";
	int idx = 0, cnt = vec.size();
	for(int i = 1; i <= n; i++) {
		if(cnt == k) break;
		if(vec[idx] != i-1) {
			cout << i << " ";
			cnt++;
		}
		else idx++;
	}
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:52:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   52 |   if(vec.size() > k) l = m+1;
      |      ~~~~~~~~~~~^~~
Main.cpp: In function 'std::pair<long long int, long long int> dp(long long int, long long int, long long int)':
Main.cpp:26:21: warning: 'pard' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  if(res.first == -1 && res.second > v) {
      |     ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 3 ms 4988 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 30256 KB Output is correct
2 Incorrect 391 ms 31152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 3 ms 4988 KB Output isn't correct
4 Halted 0 ms 0 KB -