oj.uz

Submission #542344

# Submission time Handle Problem Language Result Execution time Memory
542344 2022-03-26T08:52:34 Z inksamurai Parkovi (COCI22_parkovi) C++17
110 / 110
 1885 ms 57320 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3ulnVOy ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<"\n";}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

const int inf=1e9+11;
const ll lnf=1e15+11;
using pll=pair<ll,ll>;
using vp=vec(pll);

signed main(){
_3ulnVOy;
	int n,k;
	cin>>n>>k;
	vec(vp) adj(n);
	rep(i,n-1){
		int u,v,w;
		cin>>u>>v>>w;
		u-=1,v-=1;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}

	int cnt=0;
	vi pns;
	auto dfs=[&](auto self,int v,int par,int can)->pll{
		pll now={0,-lnf}; 
		vec(pair<int,pll>) cands;
		for(auto e:adj[v]){
			auto [u,w]=e;
			if(u==par) continue;
			pll nep=self(self,u,v,can);
			if(nep.fi+w>can){
				pns.pb(u);
				now.se=max(now.se,can-w);
				cnt+=1;
			}else{
				now.se=max(now.se,nep.se-w);
				cands.pb({w,nep});
			}
		}
		for(auto tp:cands){
			ll w=tp.fi;
			pll p=tp.se;
			now.fi=max(now.fi,p.fi+w);
		}
		if(now.fi<=now.se){
			now.fi=-lnf;
		}
		return now;
	};

	auto quq=[&](int x)->bool{
		cnt=0;
		pns.clear();
		pll p=dfs(dfs,0,-1,x);
		if(p.fi!=-lnf){
			cnt+=1;
			pns.pb(0);
		}
		return cnt<=k;
		// print("\n...",cnt);
	};

	int c;
	{
		int l=1,r=lnf;
		while(l<=r){
			int m=(l+r)/2;
			if(quq(m)){
				c=m;
				r=m-1;
			}else{
				l=m+1;
			}
		}
		quq(c);
	}

	{
		vi usd(n,0);
		rep(i,sz(pns)){
			usd[pns[i]]=1;
		}
		rep(i,n){
			if(!usd[i] and sz(pns)<k){
				pns.pb(i);
			}
		}
	}

	print(c);
	for(auto v:pns){
		cout<<v+1<<" ";
	}
	print();
//
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 719 ms 53184 KB Output is correct
2 Correct 735 ms 54488 KB Output is correct
3 Correct 650 ms 25320 KB Output is correct
4 Correct 1661 ms 15732 KB Output is correct
5 Correct 1599 ms 15292 KB Output is correct
6 Correct 1605 ms 15312 KB Output is correct
7 Correct 1613 ms 15476 KB Output is correct
8 Correct 1754 ms 16144 KB Output is correct
9 Correct 1677 ms 15768 KB Output is correct
10 Correct 1734 ms 16100 KB Output is correct
11 Correct 1066 ms 19616 KB Output is correct
12 Correct 1029 ms 20008 KB Output is correct
13 Correct 1149 ms 22192 KB Output is correct
14 Correct 1049 ms 19964 KB Output is correct
15 Correct 1008 ms 18792 KB Output is correct
16 Correct 1039 ms 20288 KB Output is correct
17 Correct 1040 ms 18772 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 55632 KB Output is correct
2 Correct 724 ms 53908 KB Output is correct
3 Correct 714 ms 51208 KB Output is correct
4 Correct 702 ms 51240 KB Output is correct
5 Correct 648 ms 54564 KB Output is correct
6 Correct 726 ms 54648 KB Output is correct
7 Correct 737 ms 56636 KB Output is correct
8 Correct 837 ms 55916 KB Output is correct
9 Correct 765 ms 55408 KB Output is correct
10 Correct 800 ms 54220 KB Output is correct
11 Correct 822 ms 52268 KB Output is correct
12 Correct 769 ms 56584 KB Output is correct
13 Correct 779 ms 57320 KB Output is correct
14 Correct 718 ms 55868 KB Output is correct
15 Correct 719 ms 54176 KB Output is correct
16 Correct 694 ms 51916 KB Output is correct
17 Correct 682 ms 51888 KB Output is correct
18 Correct 747 ms 54604 KB Output is correct
19 Correct 678 ms 53012 KB Output is correct
20 Correct 711 ms 54872 KB Output is correct
21 Correct 725 ms 53700 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 719 ms 53184 KB Output is correct
16 Correct 735 ms 54488 KB Output is correct
17 Correct 650 ms 25320 KB Output is correct
18 Correct 1661 ms 15732 KB Output is correct
19 Correct 1599 ms 15292 KB Output is correct
20 Correct 1605 ms 15312 KB Output is correct
21 Correct 1613 ms 15476 KB Output is correct
22 Correct 1754 ms 16144 KB Output is correct
23 Correct 1677 ms 15768 KB Output is correct
24 Correct 1734 ms 16100 KB Output is correct
25 Correct 1066 ms 19616 KB Output is correct
26 Correct 1029 ms 20008 KB Output is correct
27 Correct 1149 ms 22192 KB Output is correct
28 Correct 1049 ms 19964 KB Output is correct
29 Correct 1008 ms 18792 KB Output is correct
30 Correct 1039 ms 20288 KB Output is correct
31 Correct 1040 ms 18772 KB Output is correct
32 Correct 738 ms 55632 KB Output is correct
33 Correct 724 ms 53908 KB Output is correct
34 Correct 714 ms 51208 KB Output is correct
35 Correct 702 ms 51240 KB Output is correct
36 Correct 648 ms 54564 KB Output is correct
37 Correct 726 ms 54648 KB Output is correct
38 Correct 737 ms 56636 KB Output is correct
39 Correct 837 ms 55916 KB Output is correct
40 Correct 765 ms 55408 KB Output is correct
41 Correct 800 ms 54220 KB Output is correct
42 Correct 822 ms 52268 KB Output is correct
43 Correct 769 ms 56584 KB Output is correct
44 Correct 779 ms 57320 KB Output is correct
45 Correct 718 ms 55868 KB Output is correct
46 Correct 719 ms 54176 KB Output is correct
47 Correct 694 ms 51916 KB Output is correct
48 Correct 682 ms 51888 KB Output is correct
49 Correct 747 ms 54604 KB Output is correct
50 Correct 678 ms 53012 KB Output is correct
51 Correct 711 ms 54872 KB Output is correct
52 Correct 725 ms 53700 KB Output is correct
53 Correct 1633 ms 15616 KB Output is correct
54 Correct 1728 ms 16040 KB Output is correct
55 Correct 1885 ms 16772 KB Output is correct
56 Correct 1797 ms 16528 KB Output is correct
57 Correct 1711 ms 17168 KB Output is correct
58 Correct 1723 ms 15744 KB Output is correct
59 Correct 1477 ms 17940 KB Output is correct
60 Correct 1857 ms 16736 KB Output is correct
61 Correct 1576 ms 15264 KB Output is correct
62 Correct 1543 ms 16352 KB Output is correct
63 Correct 1810 ms 16840 KB Output is correct
64 Correct 1649 ms 17300 KB Output is correct
65 Correct 1811 ms 16228 KB Output is correct
66 Correct 1521 ms 16572 KB Output is correct
67 Correct 1561 ms 15380 KB Output is correct
68 Correct 1591 ms 18156 KB Output is correct
69 Correct 712 ms 54364 KB Output is correct
70 Correct 688 ms 51644 KB Output is correct
71 Correct 734 ms 57036 KB Output is correct
72 Correct 640 ms 24356 KB Output is correct
73 Correct 613 ms 25516 KB Output is correct
74 Correct 620 ms 25060 KB Output is correct
75 Correct 1067 ms 20968 KB Output is correct
76 Correct 1114 ms 21460 KB Output is correct
77 Correct 1079 ms 20560 KB Output is correct
78 Correct 1073 ms 21636 KB Output is correct