oj.uz

Submission #424107

# Submission time Handle Problem Language Result Execution time Memory
424107 2021-06-11T16:46:21 Z lyc Treatment Project (JOI20_treatment) C++14
0 / 100
 139 ms 47772 KB 
#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.R < b.R; });
    FOR(i,1,M){
        FOR(j,i+1,M){
            auto x = treat[i], y = treat[j];
            if (x.R < y.R && x.R-abs(y.T-x.T) >= y.L-1) am[i][j] = y.C;
            else am[i][j] = -1;
            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.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 47772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Incorrect 1 ms 1484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Incorrect 1 ms 1484 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 47772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -