Submission #783629

#TimeUsernameProblemLanguageResultExecution timeMemory
783629cig32Parkovi (COCI22_parkovi)C++17
30 / 110
186 ms39168 KiB
#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 (stderr)

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;
      |            ~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...