oj.uz

Submission #783629

# Submission time Handle Problem Language Result Execution time Memory
783629 2023-07-15T06:50:20 Z cig32 Parkovi (COCI22_parkovi) C++17
30 / 110
 186 ms 39168 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;
  }
  if(moments.size() < k) {
    int ptr = 0;
    for(int i=1; i<=n; i++) {
      if(ptr < moments.size() && moments[ptr] == i) {
        ptr++;
      }
      else {
        moments.push_back(i);
        if(moments.size() == k) break;
      }
    }
  }
  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);
}
// 勿忘初衷

Compilation message

Main.cpp: In function 'std::pair<long long int, std::vector<long long int> > find(long long int)':
Main.cpp:44:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   44 |   if(moments.size() < k) {
      |      ~~~~~~~~~~~~~~~^~~
Main.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |       if(ptr < moments.size() && moments[ptr] == i) {
      |          ~~~~^~~~~~~~~~~~~~~~
Main.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   52 |         if(moments.size() == k) break;
      |            ~~~~~~~~~~~~~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 12 ms 23756 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 33980 KB Output is correct
2 Correct 68 ms 34344 KB Output is correct
3 Incorrect 76 ms 34588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 34432 KB Output is correct
2 Correct 77 ms 34212 KB Output is correct
3 Correct 65 ms 33616 KB Output is correct
4 Correct 65 ms 33692 KB Output is correct
5 Correct 152 ms 38852 KB Output is correct
6 Correct 131 ms 36520 KB Output is correct
7 Correct 125 ms 37568 KB Output is correct
8 Correct 67 ms 34504 KB Output is correct
9 Correct 64 ms 34504 KB Output is correct
10 Correct 75 ms 34256 KB Output is correct
11 Correct 77 ms 33856 KB Output is correct
12 Correct 186 ms 39168 KB Output is correct
13 Correct 162 ms 38644 KB Output is correct
14 Correct 126 ms 36684 KB Output is correct
15 Correct 61 ms 34196 KB Output is correct
16 Correct 58 ms 33760 KB Output is correct
17 Correct 66 ms 34064 KB Output is correct
18 Correct 61 ms 34256 KB Output is correct
19 Correct 144 ms 38492 KB Output is correct
20 Correct 132 ms 38248 KB Output is correct
21 Correct 108 ms 36512 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23788 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Incorrect 12 ms 23756 KB Output isn't correct
5 Halted 0 ms 0 KB -