# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
671162 |
2022-12-12T09:00:45 Z |
neki |
Parkovi (COCI22_parkovi) |
C++14 |
|
1369 ms |
45136 KB |
#include <bits/stdc++.h>
#define ll long long
#define vc vector
using namespace std;
int main() {
ll n, k; cin >> n >> k;
vc<vc<pair<ll, ll>>> edg(n+1);
ll sum=0;
for(ll i=1;i<n;++i){
ll a, b, w;cin >> a >> b >> w;
sum+=w;
edg[a].emplace_back(b, w);
edg[b].emplace_back(a, w);
}
ll l=0, r=sum, cnt=0;
vc<ll> ans(n+1, 0);
function<ll (ll)> solve=[&](ll d){
ans.assign(n+1, 0);
cnt=0;
function<pair<ll, ll> (ll, ll, ll)> dfs=[&](ll u, ll p, ll w){
ll bm=0, m, M=0;
for(auto v: edg[u])if(v.first!=p){
auto q=dfs(v.first, u, v.second);
if(q.first){
if(bm) m=min(m, q.second);
else bm=1, m=q.second;
}
else M=max(M, q.second);
}
if(p==-1){
if(bm && m+M<=d) return make_pair(0LL, 0LL);
++cnt; ans[u]=1;
return make_pair(1LL, 0LL);
}
if(bm){
if(m+M<=d) return make_pair(1LL, m+w);
if(M+w<=d) return make_pair(0LL, M+w);
++cnt;ans[u]=1;
//dodamo park v u
return make_pair(1LL, w);
}
else{
if(M+w<=d) return make_pair(0LL, M+w);
++cnt;ans[u]=1;
//dodamo park v u
return make_pair(1LL, w);
}
};
dfs(1, -1, 0);
return cnt<=k;
};
if(n==1){
cout << 0 << endl;
cout << 1 << endl;
return 0;
}
/*for(ll i=0;i<sum;++i){
cout << i<<": " <<solve(i)<<endl;
}*/
while(l<r){
ll mid=(l+r)/2;
if(solve(mid)) r=mid;
else l=mid+1;
}
cout << l << endl;solve(l);
for(ll i=1;i<=n;++i) if(cnt<k && ans[i]==0) ans[i]=1, ++cnt;
for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
70 | for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
| ^~~
Main.cpp:70:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
70 | for(ll i=1;i<=n;++i) if(ans[i]) cout << i << " ";cout << endl;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 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 |
1 ms |
296 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 |
1 ms |
296 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
313 ms |
41276 KB |
Output is correct |
2 |
Correct |
515 ms |
43776 KB |
Output is correct |
3 |
Correct |
454 ms |
20360 KB |
Output is correct |
4 |
Correct |
1237 ms |
19936 KB |
Output is correct |
5 |
Correct |
1201 ms |
19300 KB |
Output is correct |
6 |
Correct |
1180 ms |
19312 KB |
Output is correct |
7 |
Correct |
661 ms |
18224 KB |
Output is correct |
8 |
Correct |
686 ms |
19120 KB |
Output is correct |
9 |
Correct |
1212 ms |
19460 KB |
Output is correct |
10 |
Correct |
1242 ms |
19792 KB |
Output is correct |
11 |
Correct |
783 ms |
22052 KB |
Output is correct |
12 |
Correct |
740 ms |
22164 KB |
Output is correct |
13 |
Correct |
841 ms |
24212 KB |
Output is correct |
14 |
Correct |
445 ms |
20624 KB |
Output is correct |
15 |
Correct |
441 ms |
19948 KB |
Output is correct |
16 |
Correct |
744 ms |
21840 KB |
Output is correct |
17 |
Correct |
721 ms |
20652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
515 ms |
44552 KB |
Output is correct |
2 |
Correct |
484 ms |
43320 KB |
Output is correct |
3 |
Correct |
443 ms |
41108 KB |
Output is correct |
4 |
Correct |
445 ms |
41016 KB |
Output is correct |
5 |
Correct |
505 ms |
43724 KB |
Output is correct |
6 |
Correct |
528 ms |
43596 KB |
Output is correct |
7 |
Correct |
550 ms |
45136 KB |
Output is correct |
8 |
Correct |
470 ms |
44076 KB |
Output is correct |
9 |
Correct |
473 ms |
43784 KB |
Output is correct |
10 |
Correct |
484 ms |
42932 KB |
Output is correct |
11 |
Correct |
441 ms |
41320 KB |
Output is correct |
12 |
Correct |
514 ms |
44556 KB |
Output is correct |
13 |
Correct |
512 ms |
45056 KB |
Output is correct |
14 |
Correct |
512 ms |
44244 KB |
Output is correct |
15 |
Correct |
296 ms |
42140 KB |
Output is correct |
16 |
Correct |
280 ms |
40396 KB |
Output is correct |
17 |
Correct |
286 ms |
40248 KB |
Output is correct |
18 |
Correct |
291 ms |
42352 KB |
Output is correct |
19 |
Correct |
310 ms |
41172 KB |
Output is correct |
20 |
Correct |
304 ms |
42448 KB |
Output is correct |
21 |
Correct |
302 ms |
41548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 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 |
1 ms |
296 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 |
1 ms |
296 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
313 ms |
41276 KB |
Output is correct |
16 |
Correct |
515 ms |
43776 KB |
Output is correct |
17 |
Correct |
454 ms |
20360 KB |
Output is correct |
18 |
Correct |
1237 ms |
19936 KB |
Output is correct |
19 |
Correct |
1201 ms |
19300 KB |
Output is correct |
20 |
Correct |
1180 ms |
19312 KB |
Output is correct |
21 |
Correct |
661 ms |
18224 KB |
Output is correct |
22 |
Correct |
686 ms |
19120 KB |
Output is correct |
23 |
Correct |
1212 ms |
19460 KB |
Output is correct |
24 |
Correct |
1242 ms |
19792 KB |
Output is correct |
25 |
Correct |
783 ms |
22052 KB |
Output is correct |
26 |
Correct |
740 ms |
22164 KB |
Output is correct |
27 |
Correct |
841 ms |
24212 KB |
Output is correct |
28 |
Correct |
445 ms |
20624 KB |
Output is correct |
29 |
Correct |
441 ms |
19948 KB |
Output is correct |
30 |
Correct |
744 ms |
21840 KB |
Output is correct |
31 |
Correct |
721 ms |
20652 KB |
Output is correct |
32 |
Correct |
515 ms |
44552 KB |
Output is correct |
33 |
Correct |
484 ms |
43320 KB |
Output is correct |
34 |
Correct |
443 ms |
41108 KB |
Output is correct |
35 |
Correct |
445 ms |
41016 KB |
Output is correct |
36 |
Correct |
505 ms |
43724 KB |
Output is correct |
37 |
Correct |
528 ms |
43596 KB |
Output is correct |
38 |
Correct |
550 ms |
45136 KB |
Output is correct |
39 |
Correct |
470 ms |
44076 KB |
Output is correct |
40 |
Correct |
473 ms |
43784 KB |
Output is correct |
41 |
Correct |
484 ms |
42932 KB |
Output is correct |
42 |
Correct |
441 ms |
41320 KB |
Output is correct |
43 |
Correct |
514 ms |
44556 KB |
Output is correct |
44 |
Correct |
512 ms |
45056 KB |
Output is correct |
45 |
Correct |
512 ms |
44244 KB |
Output is correct |
46 |
Correct |
296 ms |
42140 KB |
Output is correct |
47 |
Correct |
280 ms |
40396 KB |
Output is correct |
48 |
Correct |
286 ms |
40248 KB |
Output is correct |
49 |
Correct |
291 ms |
42352 KB |
Output is correct |
50 |
Correct |
310 ms |
41172 KB |
Output is correct |
51 |
Correct |
304 ms |
42448 KB |
Output is correct |
52 |
Correct |
302 ms |
41548 KB |
Output is correct |
53 |
Correct |
1176 ms |
19760 KB |
Output is correct |
54 |
Correct |
1254 ms |
20348 KB |
Output is correct |
55 |
Correct |
1303 ms |
21216 KB |
Output is correct |
56 |
Correct |
1275 ms |
20844 KB |
Output is correct |
57 |
Correct |
1268 ms |
20920 KB |
Output is correct |
58 |
Correct |
1135 ms |
20024 KB |
Output is correct |
59 |
Correct |
1369 ms |
21988 KB |
Output is correct |
60 |
Correct |
677 ms |
19828 KB |
Output is correct |
61 |
Correct |
586 ms |
18032 KB |
Output is correct |
62 |
Correct |
607 ms |
18400 KB |
Output is correct |
63 |
Correct |
655 ms |
19820 KB |
Output is correct |
64 |
Correct |
665 ms |
19788 KB |
Output is correct |
65 |
Correct |
1167 ms |
20064 KB |
Output is correct |
66 |
Correct |
1208 ms |
19768 KB |
Output is correct |
67 |
Correct |
1071 ms |
18816 KB |
Output is correct |
68 |
Correct |
1298 ms |
21328 KB |
Output is correct |
69 |
Correct |
502 ms |
43740 KB |
Output is correct |
70 |
Correct |
444 ms |
40800 KB |
Output is correct |
71 |
Correct |
510 ms |
44856 KB |
Output is correct |
72 |
Correct |
356 ms |
19128 KB |
Output is correct |
73 |
Correct |
244 ms |
18724 KB |
Output is correct |
74 |
Correct |
268 ms |
19360 KB |
Output is correct |
75 |
Correct |
749 ms |
22860 KB |
Output is correct |
76 |
Correct |
455 ms |
22328 KB |
Output is correct |
77 |
Correct |
723 ms |
21964 KB |
Output is correct |
78 |
Correct |
448 ms |
21624 KB |
Output is correct |