Submission #848411

#TimeUsernameProblemLanguageResultExecution timeMemory
848411belgianbotOvertaking (IOI23_overtaking)C++17
39 / 100
3558 ms516 KiB
#include "overtaking.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<int> W, S; vector<long long> T; int L, N, X, M; void init(int LL, int NN, std::vector<long long> TT, std::vector<int> WW, int XX, int MM, std::vector<int> SS) { L = LL; N = NN; X = XX; M = MM; T = TT; W = WW; S = SS; return; } struct bus{ int w, n; long long t; bool operator <(const bus& a) const{ return (t < a.t || (a.t == t && w < a.w)); } bool operator >(const bus& a) const{ return (t > a.t || (a.t == t && w > a.w)); } }; long long arrival_time(long long Y) { long long ans(Y); priority_queue< bus, vector<bus>, greater<bus> >q; for (int i(0); i < N; i++) { if (T[i] < Y) { if (W[i] > X) { bus a; a.w = W[i]; a.t = T[i]; a.n = i; q.push(a); } } } for (int i(1); i < M; i++) { vector< int > blocked(N); vector< bus > next; long long latest(0); int blocking; while (!q.empty()) { bus a = q.top(); q.pop(); if (a.t + (ll)((S[i] - S[i - 1])) * (ll)(a.w) <= latest) { blocked[a.n] = blocking; } else { latest = a.t + (ll)((S[i] - S[i - 1])) * (ll)(a.w); blocking = a.n; blocked[a.n] = a.n; } a.t = latest; next.push_back(a); } int overtoken(N); if (ans + (ll)((S[i] - S[i - 1])) * (ll)(X) <= latest) { overtoken = blocking; ans = latest; } else ans += (ll)((S[i] - S[i - 1])) * (ll)(X); for (bus j : next) { if (blocked[j.n] != overtoken) q.push(j); } if (q.empty()){ ans += (ll)((S[M - 1] - S[i])) * (ll)(X); break; } } return ans; }

Compilation message (stderr)

overtaking.cpp: In function 'long long int arrival_time(long long int)':
overtaking.cpp:50:30: warning: 'blocking' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |                 blocked[a.n] = blocking;
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...