Submission #526764

#	Time	Username	Problem	Language	Result	Execution time	Memory
526764		hmm789	Parkovi (COCI22_parkovi)	C++14	110 / 110	1219 ms	32184 KiB

Main

#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);
	}
	if(par == -1) pard = 2e18;
	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, -1);
		if(vec.size() > k) l = m+1;
		else r = m;
	}
	vec.clear();
	dp(0, l, -1);
	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 (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:53: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]
   53 |   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:25:31: warning: 'pard' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |   res = make_pair(-1, mxunder + pard);
      |                       ~~~~~~~~^~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60