Submission #489908

#	Time	Username	Problem	Language	Result	Execution time	Memory
489908		blue	Treatment Project (JOI20_treatment)	C++17	35 / 100	995 ms	524292 KiB

treatment

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vl = vector<ll>;

const int mx = 5'000;

int N, M;
vi T(mx), L(mx), R(mx), C(mx);

int lw, rw;

vi edge[mx + 2];
vl wt[mx + 2];

void add_edge(int u, int v, ll w)
{
    edge[u].push_back(v);
    // edge[v].push_back(u); //check this later???
    wt[u].push_back(w);
    // wt[v].push_back(w);

    // cerr << "adding edge " << u << " -> " << v << '\n';
}

ll INF = 1'000'000'000'000'000'000LL;


vl lw_dist(mx+2, INF);

struct pos
{
    int i;
};

bool operator < (pos A, pos B)
{
    if(lw_dist[A.i] == lw_dist[B.i]) return A.i < B.i;
    return lw_dist[A.i] < lw_dist[B.i];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    for(int i = 0; i < M; i++)
    {
        cin >> T[i] >> L[i] >> R[i] >> C[i];
    }

    lw = M;
    rw = M + 1;

    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(j == i) continue;
            
            if(L[j] <= R[i] + 1 - abs(T[j] - T[i]) && R[i] + 1 - abs(T[j] - T[i]) <= R[j])
                    add_edge(i, j, C[i]);



        }
    }

    for(int i = 0; i < M; i++)
    {
        if(L[i] == 1) add_edge(lw, i, 0);

        if(R[i] == N) add_edge(i, rw, C[i]);
    }

    lw_dist[lw] = 0;
    // cerr << "check\n";

    set<pos> S;
    for(int i = 0; i < M+2; i++) S.insert(pos{i});
    while(!S.empty())
    {
        int u = S.begin()->i;
        S.erase(S.begin());

        for(int e = 0; e < int(edge[u].size()); e++)
        {
            int v = edge[u][e];
            ll w = wt[u][e];

            if(lw_dist[u] + w < lw_dist[v])
            {
                S.erase(pos{v});
                lw_dist[v] = lw_dist[u] + w;
                S.insert(pos{v});
            }
        }
    }

    if(lw_dist[rw] == INF) lw_dist[rw] = -1;
    cout << lw_dist[rw] << '\n';
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61