oj.uz

Submission #1111649

# Submission time Handle Problem Language Result Execution time Memory
1111649 2024-11-12T13:08:26 Z vako_p Parkovi (COCI22_parkovi) C++14
30 / 110
 576 ms 106900 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],dis1[mxN],d[mxN],cnt[mxN],mid;
vector<pair<int,int>> v[mxN];
vector<pair<ll,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);
	}
}

void dfs1(ll at, ll par){
	if(dis[at] <= mid){
		dis1[at] = dis[at];
		d[at] = mid;
		cnt[at] = 1;
		vis[at] = true;
		for(auto it : v[at]){
			if(it.first == par) continue;
		 	vis[it.first] = false;
		}
//		cout << "dis[at] <= mid" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
		return;
	}
	vv[at].clear();
	ll c = 1,dd = 0,dd1 = 0,dd2 = 0;
	bool ok = true; 
	for(auto it : v[at]){
		if(it.first == par) continue;
		dfs1(it.first, at);
	 	d[it.first] -= it.second;
	 	if(d[it.first] >= 0) ok = false;
	 	dis1[it.first] += it.second;
		c += cnt[it.first] - (dis1[it.first] <= mid);
		dd2 = max(dd2, dis1[it.first]);
		if(dis1[it.first] <= mid){
			vv[at].pb({dis1[it.first], it.first});
			dd1 = max(dd1, dis1[it.first]);
			vis[it.first] = false;
		}
		else dd = max(dd, d[it.first]);
	}
	if(ok){
		cnt[at] = c;
		d[at] = mid;
		dis1[at] = dd1;
		vis[at] = true;
//		cout << "did not reach node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
		return;
	}
	sort(vv[at].begin(), vv[at].end()); 
	for(auto it : vv[at]){
		if(dd < it.first){
			cnt[at] = c;
			d[at] = mid;
			dis1[at] = dd1;
			vis[at] = true;
//			cout << "did not work without node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
			return;
		}
		else dd = max(dd, d[it.second]);
	}
	cnt[at] = c - 1;
	d[at] = dd;
	dis1[at] = dd2;
//	cout << "worked without node" << at << ' ' << cnt[at] << ' ' << ' ' << d[at] << ' ' << dis1[at] << '\n';
} 

bool ok(){
	for(int i = 0; i <= n; i++) vis[i] = false;
	dfs1(1, 1);
	return (cnt[1] <= 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 = 1e16;
	while(r > l + 1){
		mid = l + (r - l) / 2;
		if(ok()) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	mid = r;
	ok();
	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--;
		}
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49744 KB Output is correct
2 Correct 17 ms 49744 KB Output is correct
3 Correct 19 ms 48720 KB Output is correct
4 Correct 19 ms 49744 KB Output is correct
5 Correct 21 ms 48892 KB Output is correct
6 Correct 22 ms 47440 KB Output is correct
7 Incorrect 23 ms 47440 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 86112 KB Output is correct
2 Correct 187 ms 82760 KB Output is correct
3 Correct 410 ms 68664 KB Output is correct
4 Incorrect 90 ms 63052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 565 ms 98628 KB Output is correct
2 Correct 550 ms 103776 KB Output is correct
3 Correct 364 ms 93512 KB Output is correct
4 Correct 173 ms 79432 KB Output is correct
5 Correct 477 ms 102600 KB Output is correct
6 Correct 507 ms 102760 KB Output is correct
7 Correct 528 ms 104520 KB Output is correct
8 Correct 512 ms 102372 KB Output is correct
9 Correct 566 ms 101908 KB Output is correct
10 Correct 387 ms 92232 KB Output is correct
11 Correct 169 ms 80200 KB Output is correct
12 Correct 533 ms 104008 KB Output is correct
13 Correct 551 ms 104620 KB Output is correct
14 Correct 576 ms 106900 KB Output is correct
15 Correct 299 ms 100372 KB Output is correct
16 Correct 293 ms 98376 KB Output is correct
17 Correct 211 ms 95304 KB Output is correct
18 Correct 146 ms 87368 KB Output is correct
19 Correct 277 ms 99740 KB Output is correct
20 Correct 319 ms 101472 KB Output is correct
21 Correct 311 ms 100352 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49744 KB Output is correct
2 Correct 17 ms 49744 KB Output is correct
3 Correct 19 ms 48720 KB Output is correct
4 Correct 19 ms 49744 KB Output is correct
5 Correct 21 ms 48892 KB Output is correct
6 Correct 22 ms 47440 KB Output is correct
7 Incorrect 23 ms 47440 KB Output isn't correct
8 Halted 0 ms 0 KB -