oj.uz

Submission #1046931

# Submission time Handle Problem Language Result Execution time Memory
1046931 2024-08-07T06:28:22 Z 변재우(#11026) Treatment Project (JOI20_treatment) C++17
0 / 100
 2 ms 616 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=5010, INF=1e18;
int N, M, T[Nmax], L[Nmax], R[Nmax], C[Nmax], D[Nmax];
vector<int> adj[Nmax];
priority_queue<pair<int, int>> PQ;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=1; i<=M; i++) {
        cin>>T[i]>>L[i]>>R[i]>>C[i];
        if(L[i]==1) adj[0].push_back(i);
        if(R[i]==N) adj[i].push_back(M+1);
    }
    for(int i=1; i<=M; i++) for(int j=i+1; j<=M; j++) {
        int l1=L[i]+max(0ll, T[j]-T[i]), r1=R[i]-max(0ll, T[j]-T[i]);
        int l2=L[j]+max(0ll, T[i]-T[j]), r2=R[j]-max(0ll, T[i]-T[j]);
        if(l1>r1 || l2>r2) continue;
        if(!(l1>r2+1 || l2>r1+1)) adj[i].push_back(j), adj[j].push_back(i);
    }
    fill(D+1, D+M+2, INF);
    PQ.push({0, 0});
    while(!PQ.empty()) {
        int curr=PQ.top().second, dist=-PQ.top().first; PQ.pop();
        if(dist!=D[curr]) continue;
        for(int next:adj[curr]) if(D[next]>D[curr]+C[next]) D[next]=D[curr]+C[next], PQ.push({-D[next], next});
    }
    if(D[M+1]==INF) cout<<-1;
    else cout<<D[M+1];
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

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