oj.uz

Submission #1111213

# Submission time Handle Problem Language Result Execution time Memory
1111213 2024-11-11T17:38:05 Z vako_p Parkovi (COCI22_parkovi) C++14
0 / 110
 3000 ms 72776 KB 
#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 = 1e15;
	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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 47184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3073 ms 69292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3056 ms 72776 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 47184 KB Time limit exceeded
2 Halted 0 ms 0 KB -