oj.uz

Submission #867758

# Submission time Handle Problem Language Result Execution time Memory
867758 2023-10-29T12:32:30 Z epicci23 Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 68432 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#pragma GCC optimize ("O3")
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

constexpr int N = 2e5 + 5;
constexpr int INF = 1e18;

int n,k;
vector<array<int,2>> v[N];
bool ok=1;
int vis[N];
int dp[N];
int depth[N];
multiset<int> s[N];
int ck;

inline void dfs(int c,int p,int d){
  if(!ok) return;
  depth[c]=d;
  s[c].clear();
  s[c].insert(d);
  for(array<int,2> x:v[c]){

  	int u=x[0],co=x[1];
    if(u==p) continue;
    dfs(u,c,d+co);
    dp[c]=min(dp[c],dp[u]);
   
    if(sz(s[c])<sz(s[u])) swap(s[c],s[u]);
    for(int y:s[u]) s[c].insert(y);
  }  

  while(!s[c].empty()){
    if(*s[c].begin() <= ck + 2*d - dp[c]) s[c].erase(s[c].find(*s[c].begin()));
    else break;
  }

  if(s[c].empty()) return;

  int u = *s[c].rbegin();
  
  if(u>ck+d){ 
  	ok=0;
  	return;
  }
  
  if(c==1){
  	vis[c]=1;
  	dp[c]=d;
  	s[c].clear();
  	return;
  }
  
  if(u-depth[p]>ck){
  	vis[c]=1;
  	dp[c]=d;
  	s[c].clear();
  	return;
  }
}

inline bool check(int x){

  ok=1;
  fill(dp,dp+N,INF);
  fill(vis,vis+N,0);
  ck=x;

  dfs(1,0,0);

  if(s[1].empty() && ok && count(vis,vis+N,1)<=k) return 1;
  return 0;
}


void solve(){

  cin >> n >> k;
  for(int i=1;i<n;i++){
  	int a,b,c;

  	cin >> a >> b >> c;
  	v[a].pb({b,c});
  	v[b].pb({a,c});
  }

  int l=0,r=(int)1e15;
 
  while(l<r){
  	int m=(l+r)/2;
  	if(check(m)) r=m;
  	else l=m+1;
  }

  cout << l << endl;

  check(l);

  vector<int> ans;
  for(int i=1;i<=n;i++) if(vis[i]) ans.pb(i);
  for(int i=1;i<=n;i++) if(!vis[i] && sz(ans)<k) ans.pb(i);
  

  for(int x:ans) cout << x << " ";
  cout << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19036 KB Output is correct
2 Correct 14 ms 19036 KB Output is correct
3 Correct 16 ms 19252 KB Output is correct
4 Correct 14 ms 19036 KB Output is correct
5 Correct 14 ms 19036 KB Output is correct
6 Correct 14 ms 19032 KB Output is correct
7 Correct 15 ms 19032 KB Output is correct
8 Correct 13 ms 19036 KB Output is correct
9 Correct 13 ms 19036 KB Output is correct
10 Correct 14 ms 19244 KB Output is correct
11 Correct 14 ms 19036 KB Output is correct
12 Correct 16 ms 19036 KB Output is correct
13 Correct 14 ms 19032 KB Output is correct
14 Correct 13 ms 19252 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1518 ms 64788 KB Output is correct
2 Correct 1244 ms 66748 KB Output is correct
3 Execution timed out 3098 ms 49588 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 67664 KB Output is correct
2 Correct 984 ms 66276 KB Output is correct
3 Correct 1091 ms 64400 KB Output is correct
4 Correct 1151 ms 64080 KB Output is correct
5 Correct 902 ms 66488 KB Output is correct
6 Correct 995 ms 66420 KB Output is correct
7 Correct 1002 ms 68176 KB Output is correct
8 Correct 1050 ms 67664 KB Output is correct
9 Correct 1055 ms 67412 KB Output is correct
10 Correct 1163 ms 66436 KB Output is correct
11 Correct 1174 ms 64852 KB Output is correct
12 Correct 1045 ms 67820 KB Output is correct
13 Correct 1062 ms 68432 KB Output is correct
14 Correct 1093 ms 67668 KB Output is correct
15 Correct 1460 ms 65980 KB Output is correct
16 Correct 1308 ms 63860 KB Output is correct
17 Correct 1364 ms 63684 KB Output is correct
18 Correct 1531 ms 66424 KB Output is correct
19 Correct 1312 ms 64592 KB Output is correct
20 Correct 1349 ms 66108 KB Output is correct
21 Correct 1383 ms 64892 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19036 KB Output is correct
2 Correct 14 ms 19036 KB Output is correct
3 Correct 16 ms 19252 KB Output is correct
4 Correct 14 ms 19036 KB Output is correct
5 Correct 14 ms 19036 KB Output is correct
6 Correct 14 ms 19032 KB Output is correct
7 Correct 15 ms 19032 KB Output is correct
8 Correct 13 ms 19036 KB Output is correct
9 Correct 13 ms 19036 KB Output is correct
10 Correct 14 ms 19244 KB Output is correct
11 Correct 14 ms 19036 KB Output is correct
12 Correct 16 ms 19036 KB Output is correct
13 Correct 14 ms 19032 KB Output is correct
14 Correct 13 ms 19252 KB Output is correct
15 Correct 1518 ms 64788 KB Output is correct
16 Correct 1244 ms 66748 KB Output is correct
17 Execution timed out 3098 ms 49588 KB Time limit exceeded
18 Halted 0 ms 0 KB -