# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
825996 | 2023-08-15T09:46:50 Z | fdnfksd | Parkovi (COCI22_parkovi) | C++14 | 1393 ms | 35032 KB |
#include<bits/stdc++.h> #define ll long long #define pb push_back #define all(x) x.begin(),x.end() #define pll pair<ll,ll> #define endl '\n' #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);} using namespace std; const int maxN=2e5+69; const int mod=1e9+7; ll n,k,dist[2][maxN]; vector<pll> adj[maxN]; bool take[maxN]; ll x,c; void dfs(ll u,ll p=0){ dist[1][u]=1e18; for(auto z:adj[u]){ ll v=z.first; if(v==p)continue; ll w=z.second; dfs(v,u); if(dist[0][v]!=-1&&dist[0][v]+w>x)dist[1][v]=0,dist[1][u]=min(dist[1][u],w),dist[0][v]=-1,c++,take[v]=1; else { if(dist[0][v]!=-1)dist[0][u]=max(dist[0][u],dist[0][v]+w); dist[1][u]=min(dist[1][u],dist[1][v]+w); } } if(dist[0][u]+dist[1][u]<=x)dist[0][u]=-1; if(u==1&&dist[0][1]!=-1)c++,take[1]=1; } bool check(){ c=0; memset(take,0,sizeof take); memset(dist,0,sizeof dist); dfs(1); return c<=k; } void Enter(){ cin>>n>>k; for(int i=1;i<n;i++){ ll u,v,w; cin>>u>>v>>w; adj[u].pb({v,w}); adj[v].pb({u,w}); } ll l=0,r=2e14+69; while(l<r){ x=l+r>>1; if(!check())l=x+1; else r=x; } x=l; check(); cout<<l<<endl; for(int i=1;i<=n&&c<k;i++)if(!take[i])take[i]=1,c++; for(int i=1;i<=n;i++)if(take[i])cout<<i<<' '; } //amogus signed main(){ open("KTREE"); cin.tie(nullptr);ios_base::sync_with_stdio(NULL); //int t=1;cin>>t;while(t--) Enter(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 8276 KB | Output is correct |
2 | Correct | 7 ms | 8276 KB | Output is correct |
3 | Correct | 7 ms | 8276 KB | Output is correct |
4 | Correct | 6 ms | 8276 KB | Output is correct |
5 | Correct | 7 ms | 8232 KB | Output is correct |
6 | Correct | 6 ms | 8228 KB | Output is correct |
7 | Correct | 6 ms | 8272 KB | Output is correct |
8 | Correct | 6 ms | 8276 KB | Output is correct |
9 | Correct | 6 ms | 8276 KB | Output is correct |
10 | Correct | 6 ms | 8224 KB | Output is correct |
11 | Correct | 6 ms | 8276 KB | Output is correct |
12 | Correct | 7 ms | 8276 KB | Output is correct |
13 | Correct | 6 ms | 8276 KB | Output is correct |
14 | Correct | 6 ms | 8236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 288 ms | 31804 KB | Output is correct |
2 | Correct | 271 ms | 32360 KB | Output is correct |
3 | Correct | 250 ms | 17600 KB | Output is correct |
4 | Correct | 860 ms | 17936 KB | Output is correct |
5 | Correct | 802 ms | 17636 KB | Output is correct |
6 | Correct | 885 ms | 17608 KB | Output is correct |
7 | Correct | 804 ms | 17720 KB | Output is correct |
8 | Correct | 991 ms | 18248 KB | Output is correct |
9 | Correct | 933 ms | 17956 KB | Output is correct |
10 | Correct | 890 ms | 18192 KB | Output is correct |
11 | Correct | 599 ms | 19244 KB | Output is correct |
12 | Correct | 576 ms | 19364 KB | Output is correct |
13 | Correct | 633 ms | 20392 KB | Output is correct |
14 | Correct | 513 ms | 19220 KB | Output is correct |
15 | Correct | 575 ms | 18820 KB | Output is correct |
16 | Correct | 637 ms | 19532 KB | Output is correct |
17 | Correct | 667 ms | 18808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 299 ms | 32880 KB | Output is correct |
2 | Correct | 281 ms | 32200 KB | Output is correct |
3 | Correct | 308 ms | 30968 KB | Output is correct |
4 | Correct | 239 ms | 30900 KB | Output is correct |
5 | Correct | 327 ms | 32912 KB | Output is correct |
6 | Correct | 348 ms | 32616 KB | Output is correct |
7 | Correct | 353 ms | 33424 KB | Output is correct |
8 | Correct | 286 ms | 33028 KB | Output is correct |
9 | Correct | 290 ms | 32912 KB | Output is correct |
10 | Correct | 301 ms | 32332 KB | Output is correct |
11 | Correct | 271 ms | 31636 KB | Output is correct |
12 | Correct | 301 ms | 33820 KB | Output is correct |
13 | Correct | 324 ms | 35032 KB | Output is correct |
14 | Correct | 313 ms | 34372 KB | Output is correct |
15 | Correct | 268 ms | 33464 KB | Output is correct |
16 | Correct | 272 ms | 32460 KB | Output is correct |
17 | Correct | 257 ms | 32372 KB | Output is correct |
18 | Correct | 295 ms | 33640 KB | Output is correct |
19 | Correct | 271 ms | 33392 KB | Output is correct |
20 | Correct | 335 ms | 33876 KB | Output is correct |
21 | Correct | 264 ms | 33380 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 8276 KB | Output is correct |
2 | Correct | 7 ms | 8276 KB | Output is correct |
3 | Correct | 7 ms | 8276 KB | Output is correct |
4 | Correct | 6 ms | 8276 KB | Output is correct |
5 | Correct | 7 ms | 8232 KB | Output is correct |
6 | Correct | 6 ms | 8228 KB | Output is correct |
7 | Correct | 6 ms | 8272 KB | Output is correct |
8 | Correct | 6 ms | 8276 KB | Output is correct |
9 | Correct | 6 ms | 8276 KB | Output is correct |
10 | Correct | 6 ms | 8224 KB | Output is correct |
11 | Correct | 6 ms | 8276 KB | Output is correct |
12 | Correct | 7 ms | 8276 KB | Output is correct |
13 | Correct | 6 ms | 8276 KB | Output is correct |
14 | Correct | 6 ms | 8236 KB | Output is correct |
15 | Correct | 288 ms | 31804 KB | Output is correct |
16 | Correct | 271 ms | 32360 KB | Output is correct |
17 | Correct | 250 ms | 17600 KB | Output is correct |
18 | Correct | 860 ms | 17936 KB | Output is correct |
19 | Correct | 802 ms | 17636 KB | Output is correct |
20 | Correct | 885 ms | 17608 KB | Output is correct |
21 | Correct | 804 ms | 17720 KB | Output is correct |
22 | Correct | 991 ms | 18248 KB | Output is correct |
23 | Correct | 933 ms | 17956 KB | Output is correct |
24 | Correct | 890 ms | 18192 KB | Output is correct |
25 | Correct | 599 ms | 19244 KB | Output is correct |
26 | Correct | 576 ms | 19364 KB | Output is correct |
27 | Correct | 633 ms | 20392 KB | Output is correct |
28 | Correct | 513 ms | 19220 KB | Output is correct |
29 | Correct | 575 ms | 18820 KB | Output is correct |
30 | Correct | 637 ms | 19532 KB | Output is correct |
31 | Correct | 667 ms | 18808 KB | Output is correct |
32 | Correct | 299 ms | 32880 KB | Output is correct |
33 | Correct | 281 ms | 32200 KB | Output is correct |
34 | Correct | 308 ms | 30968 KB | Output is correct |
35 | Correct | 239 ms | 30900 KB | Output is correct |
36 | Correct | 327 ms | 32912 KB | Output is correct |
37 | Correct | 348 ms | 32616 KB | Output is correct |
38 | Correct | 353 ms | 33424 KB | Output is correct |
39 | Correct | 286 ms | 33028 KB | Output is correct |
40 | Correct | 290 ms | 32912 KB | Output is correct |
41 | Correct | 301 ms | 32332 KB | Output is correct |
42 | Correct | 271 ms | 31636 KB | Output is correct |
43 | Correct | 301 ms | 33820 KB | Output is correct |
44 | Correct | 324 ms | 35032 KB | Output is correct |
45 | Correct | 313 ms | 34372 KB | Output is correct |
46 | Correct | 268 ms | 33464 KB | Output is correct |
47 | Correct | 272 ms | 32460 KB | Output is correct |
48 | Correct | 257 ms | 32372 KB | Output is correct |
49 | Correct | 295 ms | 33640 KB | Output is correct |
50 | Correct | 271 ms | 33392 KB | Output is correct |
51 | Correct | 335 ms | 33876 KB | Output is correct |
52 | Correct | 264 ms | 33380 KB | Output is correct |
53 | Correct | 1033 ms | 19020 KB | Output is correct |
54 | Correct | 1393 ms | 19300 KB | Output is correct |
55 | Correct | 1136 ms | 19720 KB | Output is correct |
56 | Correct | 1002 ms | 19568 KB | Output is correct |
57 | Correct | 940 ms | 19896 KB | Output is correct |
58 | Correct | 850 ms | 19224 KB | Output is correct |
59 | Correct | 971 ms | 20752 KB | Output is correct |
60 | Correct | 895 ms | 19824 KB | Output is correct |
61 | Correct | 898 ms | 18900 KB | Output is correct |
62 | Correct | 807 ms | 19432 KB | Output is correct |
63 | Correct | 1087 ms | 19860 KB | Output is correct |
64 | Correct | 896 ms | 20368 KB | Output is correct |
65 | Correct | 907 ms | 19548 KB | Output is correct |
66 | Correct | 844 ms | 19688 KB | Output is correct |
67 | Correct | 869 ms | 18984 KB | Output is correct |
68 | Correct | 1100 ms | 21052 KB | Output is correct |
69 | Correct | 272 ms | 33640 KB | Output is correct |
70 | Correct | 296 ms | 32432 KB | Output is correct |
71 | Correct | 322 ms | 34884 KB | Output is correct |
72 | Correct | 260 ms | 18336 KB | Output is correct |
73 | Correct | 308 ms | 18804 KB | Output is correct |
74 | Correct | 249 ms | 19488 KB | Output is correct |
75 | Correct | 728 ms | 20952 KB | Output is correct |
76 | Correct | 743 ms | 21468 KB | Output is correct |
77 | Correct | 650 ms | 20860 KB | Output is correct |
78 | Correct | 613 ms | 21036 KB | Output is correct |