Submission #1111211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111211		vako_p	Parkovi (COCI22_parkovi)	C++14	0 / 110	3054 ms	74312 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,k,dis[mxN],mid;
vector<pair<int,int>> v[mxN];
vector<vector<ll>> vv[mxN];
bool vis[mxN];

void dfs(ll at, ll par){
	for(auto it : v[at]){
		if(it.first == par) continue;
		dfs(it.first, at);
		dis[at] = max(dis[at], dis[it.first] + it.second);
	}
}

pair<ll,ll> dfs1(ll at, ll d, ll par, ll op){
	bool ok = false;
	if(dis[at] <= d) return {0, 0};
	if(dis[at] <= mid){
		if(op) vis[at] = true;
		return {1, mid};	
	} 
	if(d < 0){
		d = 0;
		ok = true;
	}
	ll c1 = 1,d1 = d;
	vv[at].clear();
	for(auto it : v[at]){
		if(it.first == par) continue;
		auto x = dfs1(it.first, mid - it.second, at, 0).first;
		c1 += x;
		ll l = -1, r = mid;
		while(r > l + 1){
			ll mid1 = l + (r - l) / 2;
			if(dfs1(it.first, mid1 - it.second, at, 0).first == x) r = mid1;
			else l = mid1;
		}
		vv[at].pb({r, it.first, it.second});
	}	
	sort(vv[at].begin(), vv[at].end());
	for(auto it : vv[at]){
		if(it[0] > d){
			if(op) vis[at] = true;
			if(op) for(auto it : v[at]){
				if(it.first == par) continue;
				dfs1(it.first, mid - it.second, at, 1);
			}
			return {c1, mid};
//			cout << at << ' ' << d << ' ' << c1 << ' ' << mid << '\n';
		}
		else{
			ll x = dfs1(it[1], d - it[2], at, 0).second - it[2]; 
			if(x >= 0) ok = false;
			d = max(d, x);
		}
	}
	if(ok){
		if(op) vis[at] = true;
		if(op) for(auto it : v[at]){
			if(it.first == par) continue;
			dfs1(it.first, mid - it.second, at, 1);
		}
		return {c1, mid};
	}
//	cout << "--> " << at << ' ' << d1 << ' ' << c1 - 1 << ' ' << d << ' ' << mid << '\n';
	if(op)for(auto it : vv[at]){
		dfs1(it[1], d - it[2], at, 1); 
	}
	return {c1 - 1, d};
}

bool ok(ll op){
	return (dfs1(1, 0, 1, op).first <= k);
}

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for(int i = 0; i < n - 1; i++){
		ll a,b,w;
		cin >> a >> b >> w;
		v[a].pb({b, w});
		v[b].pb({a, w});
	}
	dfs(1, 1);
	ll l = -1, r = 1e18;
	while(r > l + 1){
		mid = l + (r - l) / 2;
		if(ok(0)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	mid = r;
	ok(1);
	ll cc = k;
	for(int i = 1; i <= n; i++){
		if(vis[i]){
			cout << i << ' ';
			cc--;
		}
	}
	for(int i = 1; i <= n and cc > 0; i++){
		if(!vis[i]){
			cout << i << ' ';
			cc--;
		}
	}
}

Compilation message (stderr)

Main.cpp: In function 'std::pair<long long int, long long int> dfs1(long long int, long long int, long long int, long long int)':
Main.cpp:31:12: warning: unused variable 'd1' [-Wunused-variable]
   31 |  ll c1 = 1,d1 = d;
      |            ^~

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