oj.uz

Submission #899382

# Submission time Handle Problem Language Result Execution time Memory
899382 2024-01-06T00:56:07 Z box Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 198672 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl
#else
#define bug(x)
#define cerr if (0) cerr
#endif

#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;

vector<i64> calculate_necessary_time(int N, int M, i64 S, int Q, vi A, vi B, vector<i64> L, vector<i64> C, vi U, vi V, vector<i64> T) {
    const int MAXN = 90;
    const i64 INF = 1e18;
    static vi adj[MAXN];
    for (int i = 0; i < M; i++) adj[A[i]].push_back(i), adj[B[i]].push_back(i);
    static i64 dist[MAXN][MAXN], end[MAXN][MAXN];
    for (int src = 0; src < N; src++) {
        {
            fill(dist[src], dist[src] + N, INF);
            using X = pair<i64, int>;
            priority_queue<X, vector<X>, greater<X>> pq;
            auto ins = [&](int i, i64 d) {
                if (dist[src][i] > d)
                    pq.push({dist[src][i] = d, i});
            };
            ins(src, 0);
            while (sz(pq)) {
                auto [d, i] = pq.top(); pq.pop();
                if (dist[src][i] != d) continue;
                for (int h : adj[i]) ins(i ^ A[h] ^ B[h], L[h] + (d % S <= C[h] - L[h] ? d : (d / S + 1) * S));
            }
        }
        {
            fill(end[src], end[src] + N, -1);
            using X = pair<i64, int>;
            priority_queue<X> pq;
            auto ins = [&](int i, i64 d) {
                if (end[src][i] < d)
                    pq.push({end[src][i] = d, i});
            };
            ins(src, S);
            while (sz(pq)) {
                auto [d, i] = pq.top(); pq.pop();
                if (end[src][i] != d) continue;
                for (int h : adj[i]) ins(i ^ A[h] ^ B[h], min(C[h], d) - L[h]);
            }
        }

    }
    vector<i64> ans(Q);
    static vi at_v[MAXN];
    for (int i = 0; i < Q; i++) {
        i64 x = INF;
        for (int j = 0; j < N; j++) if (T[i] <= end[j][U[i]]) x = min(x, S - T[i] + dist[j][V[i]]);
        ans[i] = x;
        if (dist[U[i]][V[i]] <= S) at_v[U[i]].push_back(i);
    }
    for (int src = 0; src < N; src++) {
        static i64 dist[MAXN];
        static bool consider[MAXN];
        fill(dist, dist + N, INF);
        fill(consider, consider + N, false);
        auto upd = [&](int i, i64 d) {
            if (dist[i] > d) {
                dist[i] = d;
                consider[i] = 1;
            }
        };
        i64 START = INF;
        priority_queue<pair<i64, pi>> edges;
        auto relax = [&]() {
            while (1) {
                int i = -1;
                for (int j = 0; j < N; j++) if (consider[j] && (i == -1 || dist[j] < dist[i])) i = j;
                if (i == -1) return;
                consider[i] = 0;
                for (int h : adj[i]) {
                    int j = i ^ A[h] ^ B[h];
                    if (dist[j] <= dist[i] + L[h]) continue;
                    if (START + dist[i] + L[h] <= C[h]) upd(j, dist[i] + L[h]);
                    else edges.push({C[h] - dist[i] - L[h], {i, h}});
                }
            }
        };
        upd(src, 0);
        sort(all(at_v[src]), [&](int i, int j) {
            return T[i] > T[j];
        });
        for (int i : at_v[src]) {
            START = T[i];
            while (sz(edges) && edges.top().first >= START) {
                auto [i, h] = edges.top().second; edges.pop();
                int j = i ^ A[h] ^ B[h];
                upd(j, dist[i] + L[h]);
            }
            relax();
            ans[i] = min(ans[i], dist[V[i]]);
        }
    }
    return ans;
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M, Q; i64 S; cin >> N >> M >> S >> Q;
    vi A(M), B(M); vector<i64> L(M), C(M);
    for (int i = 0; i < M; i++) cin >> A[i] >> B[i] >> L[i] >> C[i];
    vi U(Q), V(Q); vector<i64> T(Q);
    for (int i = 0; i < Q; i++) cin >> U[i] >> V[i] >> T[i];
    auto ans = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
    assert(sz(ans) == Q);
    for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Correct 10 ms 65140 KB Output is correct
3 Correct 14 ms 65112 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 160532 KB Output is correct
2 Correct 1152 ms 184324 KB Output is correct
3 Correct 1108 ms 164292 KB Output is correct
4 Correct 1181 ms 192276 KB Output is correct
5 Correct 1162 ms 192784 KB Output is correct
6 Correct 8 ms 65112 KB Output is correct
7 Correct 1116 ms 164176 KB Output is correct
8 Correct 320 ms 191700 KB Output is correct
9 Correct 1092 ms 152912 KB Output is correct
10 Correct 1169 ms 192212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Correct 10 ms 65140 KB Output is correct
3 Correct 14 ms 65112 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1110 ms 160532 KB Output is correct
8 Correct 1152 ms 184324 KB Output is correct
9 Correct 1108 ms 164292 KB Output is correct
10 Correct 1181 ms 192276 KB Output is correct
11 Correct 1162 ms 192784 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 1116 ms 164176 KB Output is correct
14 Correct 320 ms 191700 KB Output is correct
15 Correct 1092 ms 152912 KB Output is correct
16 Correct 1169 ms 192212 KB Output is correct
17 Correct 1137 ms 163276 KB Output is correct
18 Correct 1231 ms 162000 KB Output is correct
19 Correct 1326 ms 186000 KB Output is correct
20 Correct 1018 ms 165912 KB Output is correct
21 Correct 1364 ms 194132 KB Output is correct
22 Correct 1359 ms 194872 KB Output is correct
23 Correct 1022 ms 165340 KB Output is correct
24 Correct 408 ms 193976 KB Output is correct
25 Correct 1119 ms 155012 KB Output is correct
26 Correct 1363 ms 194352 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Correct 10 ms 65140 KB Output is correct
3 Correct 14 ms 65112 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1110 ms 160532 KB Output is correct
8 Correct 1152 ms 184324 KB Output is correct
9 Correct 1108 ms 164292 KB Output is correct
10 Correct 1181 ms 192276 KB Output is correct
11 Correct 1162 ms 192784 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 1116 ms 164176 KB Output is correct
14 Correct 320 ms 191700 KB Output is correct
15 Correct 1092 ms 152912 KB Output is correct
16 Correct 1169 ms 192212 KB Output is correct
17 Correct 1137 ms 163276 KB Output is correct
18 Correct 1231 ms 162000 KB Output is correct
19 Correct 1326 ms 186000 KB Output is correct
20 Correct 1018 ms 165912 KB Output is correct
21 Correct 1364 ms 194132 KB Output is correct
22 Correct 1359 ms 194872 KB Output is correct
23 Correct 1022 ms 165340 KB Output is correct
24 Correct 408 ms 193976 KB Output is correct
25 Correct 1119 ms 155012 KB Output is correct
26 Correct 1363 ms 194352 KB Output is correct
27 Correct 2056 ms 164888 KB Output is correct
28 Correct 3087 ms 166400 KB Output is correct
29 Correct 3716 ms 187952 KB Output is correct
30 Correct 1146 ms 167008 KB Output is correct
31 Correct 3668 ms 198216 KB Output is correct
32 Correct 3743 ms 197748 KB Output is correct
33 Correct 416 ms 194452 KB Output is correct
34 Correct 1935 ms 155216 KB Output is correct
35 Correct 3600 ms 198672 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Correct 10 ms 65140 KB Output is correct
3 Correct 14 ms 65112 KB Output is correct
4 Correct 9 ms 65112 KB Output is correct
5 Correct 10 ms 65116 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1110 ms 160532 KB Output is correct
8 Correct 1152 ms 184324 KB Output is correct
9 Correct 1108 ms 164292 KB Output is correct
10 Correct 1181 ms 192276 KB Output is correct
11 Correct 1162 ms 192784 KB Output is correct
12 Correct 8 ms 65112 KB Output is correct
13 Correct 1116 ms 164176 KB Output is correct
14 Correct 320 ms 191700 KB Output is correct
15 Correct 1092 ms 152912 KB Output is correct
16 Correct 1169 ms 192212 KB Output is correct
17 Correct 1137 ms 163276 KB Output is correct
18 Correct 1231 ms 162000 KB Output is correct
19 Correct 1326 ms 186000 KB Output is correct
20 Correct 1018 ms 165912 KB Output is correct
21 Correct 1364 ms 194132 KB Output is correct
22 Correct 1359 ms 194872 KB Output is correct
23 Correct 1022 ms 165340 KB Output is correct
24 Correct 408 ms 193976 KB Output is correct
25 Correct 1119 ms 155012 KB Output is correct
26 Correct 1363 ms 194352 KB Output is correct
27 Correct 2056 ms 164888 KB Output is correct
28 Correct 3087 ms 166400 KB Output is correct
29 Correct 3716 ms 187952 KB Output is correct
30 Correct 1146 ms 167008 KB Output is correct
31 Correct 3668 ms 198216 KB Output is correct
32 Correct 3743 ms 197748 KB Output is correct
33 Correct 416 ms 194452 KB Output is correct
34 Correct 1935 ms 155216 KB Output is correct
35 Correct 3600 ms 198672 KB Output is correct
36 Correct 7415 ms 174160 KB Output is correct
37 Execution timed out 9068 ms 155784 KB Time limit exceeded
38 Halted 0 ms 0 KB -