oj.uz

Submission #867755

# Submission time Handle Problem Language Result Execution time Memory
867755 2023-10-29T12:30:34 Z epicci23 Parkovi (COCI22_parkovi) C++17
40 / 110
 3000 ms 79388 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#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;

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;
  }
}

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 15 ms 19036 KB Output is correct
3 Correct 15 ms 19036 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 15 ms 19036 KB Output is correct
6 Correct 15 ms 19252 KB Output is correct
7 Correct 16 ms 19032 KB Output is correct
8 Correct 14 ms 19036 KB Output is correct
9 Correct 15 ms 19032 KB Output is correct
10 Correct 15 ms 19248 KB Output is correct
11 Correct 15 ms 19036 KB Output is correct
12 Correct 15 ms 19036 KB Output is correct
13 Correct 14 ms 19032 KB Output is correct
14 Correct 15 ms 19192 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1742 ms 74872 KB Output is correct
2 Correct 1402 ms 77652 KB Output is correct
3 Execution timed out 3100 ms 51636 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 78828 KB Output is correct
2 Correct 1223 ms 77280 KB Output is correct
3 Correct 1301 ms 74068 KB Output is correct
4 Correct 1378 ms 74072 KB Output is correct
5 Correct 1014 ms 77152 KB Output is correct
6 Correct 1161 ms 77312 KB Output is correct
7 Correct 1140 ms 79184 KB Output is correct
8 Correct 1236 ms 78524 KB Output is correct
9 Correct 1230 ms 78068 KB Output is correct
10 Correct 1369 ms 76828 KB Output is correct
11 Correct 1356 ms 74692 KB Output is correct
12 Correct 1253 ms 78540 KB Output is correct
13 Correct 1299 ms 79388 KB Output is correct
14 Correct 1231 ms 78268 KB Output is correct
15 Correct 1654 ms 76068 KB Output is correct
16 Correct 1540 ms 73696 KB Output is correct
17 Correct 1652 ms 73488 KB Output is correct
18 Correct 1830 ms 76512 KB Output is correct
19 Correct 1528 ms 74204 KB Output is correct
20 Correct 1607 ms 76028 KB Output is correct
21 Correct 1627 ms 74876 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 15 ms 19036 KB Output is correct
3 Correct 15 ms 19036 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 15 ms 19036 KB Output is correct
6 Correct 15 ms 19252 KB Output is correct
7 Correct 16 ms 19032 KB Output is correct
8 Correct 14 ms 19036 KB Output is correct
9 Correct 15 ms 19032 KB Output is correct
10 Correct 15 ms 19248 KB Output is correct
11 Correct 15 ms 19036 KB Output is correct
12 Correct 15 ms 19036 KB Output is correct
13 Correct 14 ms 19032 KB Output is correct
14 Correct 15 ms 19192 KB Output is correct
15 Correct 1742 ms 74872 KB Output is correct
16 Correct 1402 ms 77652 KB Output is correct
17 Execution timed out 3100 ms 51636 KB Time limit exceeded
18 Halted 0 ms 0 KB -