oj.uz

Submission #899381

# Submission time Handle Problem Language Result Execution time Memory
899381 2024-01-06T00:54:09 Z box Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 200288 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse")
#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 8 ms 65116 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 15 ms 65032 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 9 ms 65168 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 1092 ms 150388 KB Output is correct
2 Correct 1157 ms 171812 KB Output is correct
3 Correct 1132 ms 156184 KB Output is correct
4 Correct 1154 ms 178972 KB Output is correct
5 Correct 1170 ms 178708 KB Output is correct
6 Correct 8 ms 65116 KB Output is correct
7 Correct 1130 ms 154704 KB Output is correct
8 Correct 312 ms 178320 KB Output is correct
9 Correct 1147 ms 152660 KB Output is correct
10 Correct 1179 ms 192776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 65116 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 15 ms 65032 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 9 ms 65168 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1092 ms 150388 KB Output is correct
8 Correct 1157 ms 171812 KB Output is correct
9 Correct 1132 ms 156184 KB Output is correct
10 Correct 1154 ms 178972 KB Output is correct
11 Correct 1170 ms 178708 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1130 ms 154704 KB Output is correct
14 Correct 312 ms 178320 KB Output is correct
15 Correct 1147 ms 152660 KB Output is correct
16 Correct 1179 ms 192776 KB Output is correct
17 Correct 1150 ms 164268 KB Output is correct
18 Correct 1229 ms 163868 KB Output is correct
19 Correct 1333 ms 187796 KB Output is correct
20 Correct 1020 ms 167236 KB Output is correct
21 Correct 1343 ms 196464 KB Output is correct
22 Correct 1440 ms 196184 KB Output is correct
23 Correct 1006 ms 166836 KB Output is correct
24 Correct 400 ms 196044 KB Output is correct
25 Correct 1137 ms 156244 KB Output is correct
26 Correct 1378 ms 196136 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 65116 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 15 ms 65032 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 9 ms 65168 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1092 ms 150388 KB Output is correct
8 Correct 1157 ms 171812 KB Output is correct
9 Correct 1132 ms 156184 KB Output is correct
10 Correct 1154 ms 178972 KB Output is correct
11 Correct 1170 ms 178708 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1130 ms 154704 KB Output is correct
14 Correct 312 ms 178320 KB Output is correct
15 Correct 1147 ms 152660 KB Output is correct
16 Correct 1179 ms 192776 KB Output is correct
17 Correct 1150 ms 164268 KB Output is correct
18 Correct 1229 ms 163868 KB Output is correct
19 Correct 1333 ms 187796 KB Output is correct
20 Correct 1020 ms 167236 KB Output is correct
21 Correct 1343 ms 196464 KB Output is correct
22 Correct 1440 ms 196184 KB Output is correct
23 Correct 1006 ms 166836 KB Output is correct
24 Correct 400 ms 196044 KB Output is correct
25 Correct 1137 ms 156244 KB Output is correct
26 Correct 1378 ms 196136 KB Output is correct
27 Correct 2024 ms 166636 KB Output is correct
28 Correct 3083 ms 167848 KB Output is correct
29 Correct 3635 ms 191076 KB Output is correct
30 Correct 1136 ms 168528 KB Output is correct
31 Correct 3688 ms 200288 KB Output is correct
32 Correct 3743 ms 199788 KB Output is correct
33 Correct 419 ms 194236 KB Output is correct
34 Correct 1946 ms 155220 KB Output is correct
35 Correct 3560 ms 198464 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 65116 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 15 ms 65032 KB Output is correct
4 Correct 8 ms 65116 KB Output is correct
5 Correct 9 ms 65168 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1092 ms 150388 KB Output is correct
8 Correct 1157 ms 171812 KB Output is correct
9 Correct 1132 ms 156184 KB Output is correct
10 Correct 1154 ms 178972 KB Output is correct
11 Correct 1170 ms 178708 KB Output is correct
12 Correct 8 ms 65116 KB Output is correct
13 Correct 1130 ms 154704 KB Output is correct
14 Correct 312 ms 178320 KB Output is correct
15 Correct 1147 ms 152660 KB Output is correct
16 Correct 1179 ms 192776 KB Output is correct
17 Correct 1150 ms 164268 KB Output is correct
18 Correct 1229 ms 163868 KB Output is correct
19 Correct 1333 ms 187796 KB Output is correct
20 Correct 1020 ms 167236 KB Output is correct
21 Correct 1343 ms 196464 KB Output is correct
22 Correct 1440 ms 196184 KB Output is correct
23 Correct 1006 ms 166836 KB Output is correct
24 Correct 400 ms 196044 KB Output is correct
25 Correct 1137 ms 156244 KB Output is correct
26 Correct 1378 ms 196136 KB Output is correct
27 Correct 2024 ms 166636 KB Output is correct
28 Correct 3083 ms 167848 KB Output is correct
29 Correct 3635 ms 191076 KB Output is correct
30 Correct 1136 ms 168528 KB Output is correct
31 Correct 3688 ms 200288 KB Output is correct
32 Correct 3743 ms 199788 KB Output is correct
33 Correct 419 ms 194236 KB Output is correct
34 Correct 1946 ms 155220 KB Output is correct
35 Correct 3560 ms 198464 KB Output is correct
36 Correct 7470 ms 169808 KB Output is correct
37 Execution timed out 9091 ms 155736 KB Time limit exceeded
38 Halted 0 ms 0 KB -