oj.uz

Submission #423827

# Submission time Handle Problem Language Result Execution time Memory
423827 2021-06-11T13:07:51 Z tqbfjotld Treatment Project (JOI20_treatment) C++14
35 / 100
 319 ms 185924 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int T[5005];
int L[5005];
int R[5005];
int C[5005];
vector<int> adjl[5005];
int dist[5005];

 main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<m; x++){
        scanf("%lld%lld%lld%lld",&T[x],&L[x],&R[x],&C[x]);
    }
    for (int x = 0; x<m; x++){
        for (int y = 0; y<m; y++){
            if (T[y]>T[x]){
                if (L[x]-T[x]-1<=R[y]-T[y]){
                    adjl[x].push_back(y);
                }
            }
            else{
                if (L[x]+T[x]-1<=R[y]+T[y]){
                    adjl[x].push_back(y);
                }
            }
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for (int x = 0; x<m; x++){
        if (R[x]==n){
            dist[x] = C[x];
            pq.push({C[x],x});
        }
        else{
            dist[x] = 999999999999999999LL;
        }
    }
    while (!pq.empty()){
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d>dist[node]) continue;
        for (auto x : adjl[node]){
            if (d+C[x]<dist[x]){
               // printf("node %lld go to %lld\n",node,x);
                dist[x] = d+C[x];
                pq.push({d+C[x],x});
            }
        }
    }
    int ans = 999999999999999999LL;
    for (int x = 0; x<m; x++){
        if (L[x]==1){
            ans = min(ans,dist[x]);
        }
    }
    printf("%lld",ans==999999999999999999LL?-1LL:ans);
}

Compilation message

treatment.cpp:12:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 |  main(){
      |  ^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
treatment.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld%lld%lld%lld",&T[x],&L[x],&R[x],&C[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 299 ms 129452 KB Output is correct
21 Correct 302 ms 129608 KB Output is correct
22 Correct 150 ms 3168 KB Output is correct
23 Correct 136 ms 3132 KB Output is correct
24 Correct 182 ms 89708 KB Output is correct
25 Correct 154 ms 63688 KB Output is correct
26 Correct 122 ms 60636 KB Output is correct
27 Correct 130 ms 75076 KB Output is correct
28 Correct 180 ms 89056 KB Output is correct
29 Correct 136 ms 62588 KB Output is correct
30 Correct 122 ms 70844 KB Output is correct
31 Correct 123 ms 75984 KB Output is correct
32 Correct 290 ms 121616 KB Output is correct
33 Correct 319 ms 185664 KB Output is correct
34 Correct 300 ms 119724 KB Output is correct
35 Correct 305 ms 121916 KB Output is correct
36 Correct 319 ms 185924 KB Output is correct
37 Correct 292 ms 119844 KB Output is correct

Subtask #4
0 / 61.0

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