oj.uz

Submission #825994

# Submission time Handle Problem Language Result Execution time Memory
825994 2023-08-15T09:46:12 Z fdnfksd Parkovi (COCI22_parkovi) C++14
10 / 110
 1169 ms 34772 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

Main.cpp: In function 'void Enter()':
Main.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         x=l+r>>1;
      |           ~^~
Main.cpp: In function 'int main()':
Main.cpp:7:54: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:5: note: in expansion of macro 'open'
   60 |     open("KTREE");
      |     ^~~~
Main.cpp:7:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:5: note: in expansion of macro 'open'
   60 |     open("KTREE");
      |     ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8344 KB Output is correct
2 Incorrect 7 ms 8236 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 289 ms 32788 KB Output is correct
2 Correct 279 ms 33464 KB Output is correct
3 Correct 270 ms 18576 KB Output is correct
4 Correct 1130 ms 19020 KB Output is correct
5 Correct 982 ms 18660 KB Output is correct
6 Correct 1033 ms 18672 KB Output is correct
7 Correct 742 ms 18708 KB Output is correct
8 Correct 869 ms 19240 KB Output is correct
9 Correct 1080 ms 18984 KB Output is correct
10 Correct 1169 ms 19212 KB Output is correct
11 Correct 553 ms 20148 KB Output is correct
12 Correct 590 ms 20384 KB Output is correct
13 Correct 713 ms 21412 KB Output is correct
14 Correct 565 ms 20252 KB Output is correct
15 Correct 670 ms 19848 KB Output is correct
16 Correct 573 ms 20468 KB Output is correct
17 Correct 531 ms 19828 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 34040 KB Output is correct
2 Correct 296 ms 33096 KB Output is correct
3 Correct 250 ms 32064 KB Output is correct
4 Correct 268 ms 31948 KB Output is correct
5 Correct 280 ms 33940 KB Output is correct
6 Correct 317 ms 33616 KB Output is correct
7 Correct 338 ms 34508 KB Output is correct
8 Correct 294 ms 34052 KB Output is correct
9 Correct 325 ms 33740 KB Output is correct
10 Correct 267 ms 33352 KB Output is correct
11 Correct 292 ms 32452 KB Output is correct
12 Incorrect 314 ms 34772 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 7 ms 8344 KB Output is correct
2 Incorrect 7 ms 8236 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -