oj.uz

Submission #825830

# Submission time Handle Problem Language Result Execution time Memory
825830 2023-08-15T08:38:49 Z karrigan Parkovi (COCI22_parkovi) C++14
110 / 110
 1258 ms 39964 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define pil pair<int,long long>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e5+9;
const long long inf=1e15;
vector<pil>a[maxn];
int n,k;
struct ver{
long long maxdis;
int num;
long long mindis;
ver (){
maxdis=0;
num=0;
mindis=inf;
}
}b[maxn];
vector<int>take;
void dfs(int u,int par,long long mid){
//cerr<<u<<'\n';
if (sz(a[u])==1&&a[u][0].fi==par){
    //cerr<<u<<'\n';
    for (auto v:a[u]){
        if (v.se>mid){
            b[u].mindis=0;
            b[u].maxdis=-1;
            //cerr<<u<<'\n';
            take.pb(u);
            b[u].num=1;
        }
        else {
            b[u].maxdis=v.se;
        }
    }
    return;
}
for (auto v:a[u]){
    if (v.fi==par)continue;
    dfs(v.fi,u,mid);
    b[u].maxdis=max(b[u].maxdis,b[v.fi].maxdis);
    b[u].num+=b[v.fi].num;
    b[u].mindis=min(b[u].mindis,b[v.fi].mindis+v.se);
}
if (b[u].mindis+b[u].maxdis<=mid){
   b[u].maxdis=-1;
}
//if (u==8)cout<<b[u].mindis<<" "<<b[u].maxdis<<'\n';
for (auto v:a[u]){
    if (v.fi==par){
        if (b[u].maxdis==-1){
            continue;
        }
        if (b[u].maxdis+v.se>mid){
            b[u].num++;
            //cerr<<u<<'\n';
            take.pb(u);
            b[u].mindis=0;
            b[u].maxdis=-1;
        }
        else {
            b[u].maxdis+=v.se;
        }
    }
}
if (u==1){
    if (b[u].maxdis!=-1){
        b[u].num++;
        take.pb(u);
        //cerr<<u<<'\n';
    }
}
}
bool check(long long mid){
take.clear();
for1(i,1,n){
b[i]=ver();
}
//cerr<<b[8].num<<'\n';
dfs(1,0,mid);
if (b[1].num>k)return false;
return true;
}
bool vis[maxn];
void push(){
for (auto v:take)vis[v]=1;
for1(i,1,n){
if (vis[i])continue;
if (sz(take)==k)break;
take.pb(i);
vis[i]=1;
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("KTREE.INP","r",stdin);
    //freopen("KTREE.OUT","w",stdout);
    cin>>n>>k;
    for1(i,1,n-1){
    int u,v;
    long long w;
    cin>>u>>v>>w;
    a[u].pb({v,w});
    a[v].pb({u,w});
    }
    long long l=0,r=2e14,ans=2e14;
    while (l<=r){
        long long mid=(l+r)/2;
        if (check(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<'\n';
    check(ans);
    push();
    for (auto v:take)cout<<v<<" ";
    //cout<<check(7);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9716 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9724 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9720 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 4 ms 9720 KB Output is correct
12 Correct 4 ms 9620 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9720 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 33092 KB Output is correct
2 Correct 339 ms 33820 KB Output is correct
3 Correct 295 ms 19480 KB Output is correct
4 Correct 1053 ms 19308 KB Output is correct
5 Correct 1048 ms 19008 KB Output is correct
6 Correct 906 ms 18940 KB Output is correct
7 Correct 923 ms 19092 KB Output is correct
8 Correct 1018 ms 19540 KB Output is correct
9 Correct 999 ms 19336 KB Output is correct
10 Correct 1116 ms 19568 KB Output is correct
11 Correct 765 ms 20616 KB Output is correct
12 Correct 628 ms 20636 KB Output is correct
13 Correct 744 ms 21700 KB Output is correct
14 Correct 582 ms 20596 KB Output is correct
15 Correct 731 ms 20260 KB Output is correct
16 Correct 674 ms 20884 KB Output is correct
17 Correct 681 ms 20176 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 34256 KB Output is correct
2 Correct 339 ms 33568 KB Output is correct
3 Correct 307 ms 32336 KB Output is correct
4 Correct 339 ms 32292 KB Output is correct
5 Correct 369 ms 35276 KB Output is correct
6 Correct 389 ms 34892 KB Output is correct
7 Correct 392 ms 35624 KB Output is correct
8 Correct 338 ms 34360 KB Output is correct
9 Correct 338 ms 34220 KB Output is correct
10 Correct 338 ms 33612 KB Output is correct
11 Correct 329 ms 32800 KB Output is correct
12 Correct 391 ms 36240 KB Output is correct
13 Correct 401 ms 39964 KB Output is correct
14 Correct 399 ms 38884 KB Output is correct
15 Correct 343 ms 36568 KB Output is correct
16 Correct 337 ms 35404 KB Output is correct
17 Correct 315 ms 35320 KB Output is correct
18 Correct 333 ms 36784 KB Output is correct
19 Correct 326 ms 37324 KB Output is correct
20 Correct 341 ms 37968 KB Output is correct
21 Correct 368 ms 37372 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9716 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9724 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9684 KB Output is correct
9 Correct 4 ms 9720 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 4 ms 9720 KB Output is correct
12 Correct 4 ms 9620 KB Output is correct
13 Correct 4 ms 9684 KB Output is correct
14 Correct 4 ms 9720 KB Output is correct
15 Correct 321 ms 33092 KB Output is correct
16 Correct 339 ms 33820 KB Output is correct
17 Correct 295 ms 19480 KB Output is correct
18 Correct 1053 ms 19308 KB Output is correct
19 Correct 1048 ms 19008 KB Output is correct
20 Correct 906 ms 18940 KB Output is correct
21 Correct 923 ms 19092 KB Output is correct
22 Correct 1018 ms 19540 KB Output is correct
23 Correct 999 ms 19336 KB Output is correct
24 Correct 1116 ms 19568 KB Output is correct
25 Correct 765 ms 20616 KB Output is correct
26 Correct 628 ms 20636 KB Output is correct
27 Correct 744 ms 21700 KB Output is correct
28 Correct 582 ms 20596 KB Output is correct
29 Correct 731 ms 20260 KB Output is correct
30 Correct 674 ms 20884 KB Output is correct
31 Correct 681 ms 20176 KB Output is correct
32 Correct 350 ms 34256 KB Output is correct
33 Correct 339 ms 33568 KB Output is correct
34 Correct 307 ms 32336 KB Output is correct
35 Correct 339 ms 32292 KB Output is correct
36 Correct 369 ms 35276 KB Output is correct
37 Correct 389 ms 34892 KB Output is correct
38 Correct 392 ms 35624 KB Output is correct
39 Correct 338 ms 34360 KB Output is correct
40 Correct 338 ms 34220 KB Output is correct
41 Correct 338 ms 33612 KB Output is correct
42 Correct 329 ms 32800 KB Output is correct
43 Correct 391 ms 36240 KB Output is correct
44 Correct 401 ms 39964 KB Output is correct
45 Correct 399 ms 38884 KB Output is correct
46 Correct 343 ms 36568 KB Output is correct
47 Correct 337 ms 35404 KB Output is correct
48 Correct 315 ms 35320 KB Output is correct
49 Correct 333 ms 36784 KB Output is correct
50 Correct 326 ms 37324 KB Output is correct
51 Correct 341 ms 37968 KB Output is correct
52 Correct 368 ms 37372 KB Output is correct
53 Correct 995 ms 23380 KB Output is correct
54 Correct 1037 ms 23892 KB Output is correct
55 Correct 1151 ms 24488 KB Output is correct
56 Correct 1248 ms 24492 KB Output is correct
57 Correct 1074 ms 25164 KB Output is correct
58 Correct 1026 ms 23484 KB Output is correct
59 Correct 1132 ms 26324 KB Output is correct
60 Correct 1134 ms 23024 KB Output is correct
61 Correct 898 ms 21836 KB Output is correct
62 Correct 930 ms 22940 KB Output is correct
63 Correct 1213 ms 22928 KB Output is correct
64 Correct 1037 ms 24288 KB Output is correct
65 Correct 1149 ms 23424 KB Output is correct
66 Correct 1089 ms 23908 KB Output is correct
67 Correct 931 ms 22504 KB Output is correct
68 Correct 1258 ms 25764 KB Output is correct
69 Correct 341 ms 38092 KB Output is correct
70 Correct 316 ms 36012 KB Output is correct
71 Correct 377 ms 39484 KB Output is correct
72 Correct 323 ms 23216 KB Output is correct
73 Correct 303 ms 22856 KB Output is correct
74 Correct 375 ms 24420 KB Output is correct
75 Correct 736 ms 25160 KB Output is correct
76 Correct 1016 ms 24564 KB Output is correct
77 Correct 1022 ms 24524 KB Output is correct
78 Correct 874 ms 24456 KB Output is correct