oj.uz

Submission #1020278

# Submission time Handle Problem Language Result Execution time Memory
1020278 2024-07-11T19:17:50 Z underwaterkillerwhale Treatment Project (JOI20_treatment) C++17
35 / 100
 496 ms 524288 KB 
#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rd);
}

const int N  = 2e5 + 7;
const int Mod =1e9 + 7;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 137;


struct Data {
    ll T, L, R, C;
};

int n, m;
Data a[N];
vector<pair<ll,ll>> ke[N];
ll Dist[N];

void solution () {
    cin >> n >> m;
    rep (i, 1, m) {
        cin >> a[i].T >> a[i].L >> a[i].R >> a[i].C;
        --a[i].L;
    }
    rep (i, 1, m)
    rep (j, 1, m) {
        if (i == j) continue;
        if (a[i].T <= a[j].T) {
            if (a[i].R + a[i].T >= a[j].L + a[j].T) ke[i].push_back({j, a[j].C});
        }
        else {
            if (a[i].R - a[i].T >= a[j].L - a[j].T) ke[i].push_back({j, a[j].C});
        }
    }
    memset(Dist, 0x3f, sizeof Dist);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
    rep (i, 1, m) {
        if (a[i].L == 0) {
            pq.push({a[i].C, i});
            Dist[i] = a[i].C;

        }
    }
    while (!pq.empty()) {
        int u = pq.top().se;
        if (a[u].R == n) {
            cout << Dist[u] <<"\n";
            return;
        }
        pq.pop();
        iter (&id, ke[u]) {
            ll v, w;
            tie (v, w) = id;
            if (Dist[v] > Dist[u] + w) {
                Dist[v] = Dist[u] + w;
                pq.push({Dist[v], v});
            }
        }
    }
    cout << -1 <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    file ("c");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
1 2
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 496 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 3 ms 6492 KB Output is correct
6 Correct 3 ms 6492 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Correct 3 ms 6700 KB Output is correct
9 Correct 3 ms 6492 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 3 ms 6492 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 3 ms 6492 KB Output is correct
14 Correct 3 ms 6492 KB Output is correct
15 Correct 3 ms 6492 KB Output is correct
16 Correct 3 ms 6492 KB Output is correct
17 Correct 3 ms 6492 KB Output is correct
18 Correct 3 ms 6492 KB Output is correct
19 Correct 3 ms 6492 KB Output is correct
20 Correct 261 ms 251988 KB Output is correct
21 Correct 261 ms 251992 KB Output is correct
22 Correct 92 ms 12112 KB Output is correct
23 Correct 91 ms 12112 KB Output is correct
24 Correct 174 ms 180740 KB Output is correct
25 Correct 129 ms 123984 KB Output is correct
26 Correct 125 ms 118612 KB Output is correct
27 Correct 149 ms 144208 KB Output is correct
28 Correct 175 ms 179284 KB Output is correct
29 Correct 126 ms 122312 KB Output is correct
30 Correct 130 ms 138068 KB Output is correct
31 Correct 141 ms 147024 KB Output is correct
32 Correct 260 ms 232876 KB Output is correct
33 Correct 328 ms 361312 KB Output is correct
34 Correct 260 ms 232836 KB Output is correct
35 Correct 250 ms 233044 KB Output is correct
36 Correct 334 ms 360956 KB Output is correct
37 Correct 265 ms 232488 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 496 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -