oj.uz

Submission #1099515

# Submission time Handle Problem Language Result Execution time Memory
1099515 2024-10-11T14:03:17 Z _8_8_ Treatment Project (JOI20_treatment) C++17
0 / 100
 3000 ms 10832 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = 2e5 + 12, MOD = (int)1e9 + 7;

const ll inf = 1e18;
ll res = inf, d[N];
int n, m;
vector<array<int, 4>> a;

bool cmp(array<int, 4> x, array<int, 4> y) {
    return make_pair(x[1], x[2]) < make_pair(y[1], y[2]);
}
vector<int> g[N];
void test() {
    cin >> n >> m;
    a.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3], d[i] = inf;
    }
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < m; j++) {
            if(i == j) continue;
            if(a[j][1] < a[i][1]) continue;
            ll inter = a[i][2] - a[j][1] + 1, val = abs(a[i][0] - a[j][0]);
            if(a[j][1] + val <= a[i][2] + 1) {
                g[i].push_back(j);
            }
        }
    }
    set<pair<ll, int>> st;
    for(int i = 0; i < m; i++) {    
        if(a[i][1] == 1) {
            st.insert({0, i});
            d[i] = a[i][3];
        }
    }
    while(!st.empty()) {
        auto [w, v] = (*st.begin());
        st.erase(st.begin());
        for(int to:g[v]) {
            if(d[to] > d[v] + a[to][3]) {
                st.erase({d[to], to});
                d[to] = d[v] + a[to][3];
                st.insert({d[to], to});
            }
        }
    }
    for(int i = 0; i < m; i++) if(a[i][2] == n){
        res = min(res, d[i]);
    }
    if(res == inf) {
        res = -1;
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    
    return 0;
}

Compilation message

treatment.cpp: In function 'void test()':
treatment.cpp:28:16: warning: unused variable 'inter' [-Wunused-variable]
   28 |             ll inter = a[i][2] - a[j][1] + 1, val = abs(a[i][0] - a[j][0]);
      |                ^~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 10832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 10832 KB Time limit exceeded
2 Halted 0 ms 0 KB -