oj.uz

Submission #825827

# Submission time Handle Problem Language Result Execution time Memory
825827 2023-08-15T08:34:59 Z karrigan Parkovi (COCI22_parkovi) C++14
10 / 110
 1220 ms 39780 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;
}
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);
    for (auto v:take)cout<<v<<" ";
    //cout<<check(7);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 4 ms 9592 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 35996 KB Output is correct
2 Correct 357 ms 38104 KB Output is correct
3 Correct 311 ms 23940 KB Output is correct
4 Correct 1211 ms 23472 KB Output is correct
5 Correct 906 ms 23036 KB Output is correct
6 Correct 1016 ms 23116 KB Output is correct
7 Correct 1018 ms 21840 KB Output is correct
8 Correct 1014 ms 22496 KB Output is correct
9 Correct 1220 ms 22864 KB Output is correct
10 Correct 1052 ms 23188 KB Output is correct
11 Correct 763 ms 24908 KB Output is correct
12 Correct 648 ms 24768 KB Output is correct
13 Correct 806 ms 26180 KB Output is correct
14 Correct 640 ms 23312 KB Output is correct
15 Correct 599 ms 22908 KB Output is correct
16 Correct 636 ms 24292 KB Output is correct
17 Correct 690 ms 23588 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 38616 KB Output is correct
2 Correct 364 ms 37800 KB Output is correct
3 Correct 315 ms 36428 KB Output is correct
4 Correct 328 ms 36292 KB Output is correct
5 Correct 355 ms 39272 KB Output is correct
6 Correct 378 ms 38760 KB Output is correct
7 Correct 396 ms 39780 KB Output is correct
8 Correct 360 ms 38176 KB Output is correct
9 Correct 347 ms 37880 KB Output is correct
10 Correct 316 ms 37308 KB Output is correct
11 Correct 352 ms 36176 KB Output is correct
12 Incorrect 385 ms 39740 KB Unexpected end of file - int32 expected
13 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Incorrect 4 ms 9592 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -