Submission #848417

#	Time	Username	Problem	Language	Result	Execution time	Memory
848417		belgianbot	Overtaking (IOI23_overtaking)	C++17	39 / 100	3541 ms	848 KiB

overtaking

#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);
        int j(next.size() - 1);
        for (; j >= 0 && blocked[next[j].n] == overtoken; j--);
        for (; j >= 0; j--)q.push(next[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;

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35