oj.uz

Submission #783627

# Submission time Handle Problem Language Result Execution time Memory
783627 2023-07-15T06:47:36 Z cig32 Parkovi (COCI22_parkovi) C++17
0 / 110
 118 ms 42976 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 1e6 + 10;
const int MOD = 998244353;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
vector<pair<int,int>> adj[MAXN];
int n, k, d[MAXN];
pair<int, vector<int> > find(int radius) {
  int used=0;
  vector<int> moments;
  for(int i=1;i<=n;i++){
    int j=i;
    int bruh = 0;
    while(j+1 <= n && bruh + d[j] <= radius) {
      bruh += d[j];
      j++;
    }
    bruh = 0;
    moments.push_back(j);
    while(j+1 <= n && bruh + d[j] <= radius) {
      bruh += d[j];
      j++;
    }
    used++;
    i = j;
  }
  return {used, moments};
}

void solve(int tc){
  cin>>n>>k;
  for(int i=1;i<n;i++){
    int a,b,w;
    cin>>a>>b>>w;
    d[i]=w;
    adj[a].push_back({b,w});
    adj[b].push_back({a,w});
  }
  int lb=1, rb=1e18;
  while(lb<rb){
    int mid=(lb+rb)>>1;
    if(find(mid).first<=k) rb=mid;
    else lb=mid+1;
  }
  pair<int,vector<int>>res=find(lb);
  cout<<lb<<"\n";
  for(int x:res.second)cout<<x<<" ";
  cout<<"\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 37076 KB Output is correct
2 Correct 79 ms 38644 KB Output is correct
3 Incorrect 99 ms 39140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 38864 KB Output is correct
2 Correct 68 ms 38368 KB Output is correct
3 Correct 76 ms 37600 KB Output is correct
4 Correct 70 ms 37688 KB Output is correct
5 Correct 116 ms 42976 KB Output is correct
6 Correct 113 ms 40648 KB Output is correct
7 Correct 113 ms 41932 KB Output is correct
8 Correct 68 ms 38332 KB Output is correct
9 Correct 76 ms 38080 KB Output is correct
10 Correct 65 ms 37896 KB Output is correct
11 Correct 65 ms 37288 KB Output is correct
12 Incorrect 118 ms 42868 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 12 ms 23764 KB Output is correct
2 Incorrect 12 ms 23820 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -