Submission #424119

#	Time	Username	Problem	Language	Result	Execution time	Memory
424119		lyc	Treatment Project (JOI20_treatment)	C++14	0 / 100	132 ms	44612 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int mxM = 100001;

int N, M;
struct Treat {
    int T, L, R, C;
} treat[mxM];

int am[5001][5001];
ll dist[mxM];
int vis[mxM];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> N >> M;
    FOR(i,1,M){
        int T, L, R, C;
        cin >> T >> L >> R >> C;
        treat[i] = {T,L,R,C};
    }

    sort(treat+1,treat+1+M,[](Treat& a, Treat& b){ return a.L < b.L; });
    FOR(i,1,M){
        FOR(j,i+1,M){
            auto x = treat[i], y = treat[j];
            if (x.R-abs(y.T-x.T) >= y.L-1) {
                am[i][j] = y.C;
                am[j][i] = x.C;
            } else am[i][j] = am[j][i] = -1;
        }
    }

    memset(dist,-1,sizeof dist);
    memset(vis,0,sizeof vis);
    FOR(i,1,M) if (treat[i].L == 1) dist[i] = treat[i].C;
    while (true) {
        int u = -1;
        FOR(i,1,M) if (!vis[i] && dist[i] != -1) {
            if (u == -1 || dist[i] < dist[u]) u = i;
        }
        if (u == -1) break;
        vis[u] = 1;
        if (treat[u].R == N) {
            cout << dist[u] << '\n';
            return 0;
        }

        FOR(v,1,M) if (am[u][v] != -1) {
            ll cur = dist[u]+am[u][v];
            if (dist[v] == -1 || cur < dist[v]) dist[v] = cur;
        }
    }

    cout << -1 << '\n';
}

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