oj.uz

Submission #723444

# Submission time Handle Problem Language Result Execution time Memory
723444 2023-04-13T19:59:08 Z piOOE Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 200384 KB 
#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C,
                                    vector<int> U, vector<int> V, vector<ll> T) {

    vector<ll> answer(q);

    vector<vector<int>> queries(n);

    for (int i = 0; i < q; ++i) {
        queries[U[i]].push_back(i);
    }

    vector<vector<pair<int, int>>> adj(n);

    for (int i = 0; i < m; ++i) {
        adj[A[i]].emplace_back(B[i], i);
        adj[B[i]].emplace_back(A[i], i);
    }

    constexpr ll inf = 3e18;

    auto dijkstra = [&](int source, ll s, bool rev = false) -> vector<ll> {
        vector<ll> dist(n, rev ? -inf : inf);
        dist[source] = s;

        vector<bool> used(n);

        for (int _ = 0; _ < n; ++_) {
            int v = -1;

            for (int i = 0; i < n; ++i) {
                if (!used[i] && (v == -1 || rev ^ (dist[i] < dist[v]))) {
                    v = i;
                }
            }

            used[v] = true;

            for (auto [to, i] : adj[v]) {
                ll d;

                if (rev) {
                    d = min(dist[v], C[i]) - L[i];
                } else {
                    d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S);
                }

                if (rev ^ (dist[to] > d)) {
                    dist[to] = d;
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            dist[i] = rev ? s - dist[i] : dist[i] - s;
        }

        return dist;
    };

    vector from(n, vector<ll>(n));

    for (int i = 0; i < n; ++i) {
        from[i] = dijkstra(i, 0);
    }

    vector dto(n, vector<ll>(n));

    for (int i = 0; i < n; ++i) {
        dto[i] = dijkstra(i, S - 1, true);
    }

    for (int i = 0; i < n; ++i) {
        vector<ll> till;
        vector<vector<ll>> dp;
        int dead = 0;

        for (int j = 0; dead < m; ++j) {
            till.push_back(0);
            dp.emplace_back();

            ll s = j > 0 ? till[j - 1] + 1 : 0;
            dead = 0;

            if (s < S) {
                vector<ll> d = dijkstra(i, s);

                for (int to = 0; to < n; ++to) {
                    if (d[to] + s >= S) {
                        d[to] = inf;
                    }
                }

                dp[j] = d;
                ll nxt = inf;

                for (int k = 0; k < m; ++k) {
                    if (d[A[k]] > d[B[k]]) {
                        swap(A[k], B[k]);
                    }

                    if (C[k] - L[k] >= d[A[k]] + s) {
                        nxt = min(nxt, C[k] - L[k] - d[A[k]] - s);
                    } else {
                        dead += 1;
                    }
                }

                till[j] = s + nxt;
            } else {
                dp[j] = vector(n, inf);
                till[j] = inf;
                dead = m;
            }
        }

        for (int j : queries[i]) {
            ll ans = inf;
            int to = V[j];

            for (int mid = 0; mid < n; ++mid) {
                ll dist = S - 1 - dto[mid][i] < T[j] ? inf : S - 1 - T[j] + 1 + from[mid][to];
                ans = min(ans, dist);
            }

            int k = lower_bound(till.begin(), till.end(), T[j]) - till.begin();

            if (k < dp.size()) {
                ans = min(ans, dp[k][to]);
            }

            answer[j] = ans;
        }
    }

    return answer;
}

Compilation message

escape_route.cpp: In function 'std::vector<long long int> calculate_necessary_time(int, int, ll, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::vector<long long int>)':
escape_route.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             if (k < dp.size()) {
      |                 ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64976 KB Output is correct
2 Correct 42 ms 65068 KB Output is correct
3 Correct 495 ms 65008 KB Output is correct
4 Correct 25 ms 65060 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 25 ms 65032 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1058 ms 112296 KB Output is correct
2 Correct 1041 ms 120952 KB Output is correct
3 Correct 1004 ms 125564 KB Output is correct
4 Correct 1148 ms 143512 KB Output is correct
5 Correct 1144 ms 143552 KB Output is correct
6 Correct 24 ms 64980 KB Output is correct
7 Correct 1010 ms 126156 KB Output is correct
8 Correct 502 ms 155904 KB Output is correct
9 Correct 1065 ms 126284 KB Output is correct
10 Correct 1158 ms 143048 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64976 KB Output is correct
2 Correct 42 ms 65068 KB Output is correct
3 Correct 495 ms 65008 KB Output is correct
4 Correct 25 ms 65060 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 25 ms 65032 KB Output is correct
7 Correct 1058 ms 112296 KB Output is correct
8 Correct 1041 ms 120952 KB Output is correct
9 Correct 1004 ms 125564 KB Output is correct
10 Correct 1148 ms 143512 KB Output is correct
11 Correct 1144 ms 143552 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1010 ms 126156 KB Output is correct
14 Correct 502 ms 155904 KB Output is correct
15 Correct 1065 ms 126284 KB Output is correct
16 Correct 1158 ms 143048 KB Output is correct
17 Correct 1352 ms 127260 KB Output is correct
18 Correct 1254 ms 127180 KB Output is correct
19 Correct 1271 ms 144256 KB Output is correct
20 Correct 1227 ms 128156 KB Output is correct
21 Correct 1377 ms 144812 KB Output is correct
22 Correct 1370 ms 145028 KB Output is correct
23 Correct 1255 ms 126680 KB Output is correct
24 Correct 717 ms 155076 KB Output is correct
25 Correct 1274 ms 123528 KB Output is correct
26 Correct 1358 ms 136916 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64976 KB Output is correct
2 Correct 42 ms 65068 KB Output is correct
3 Correct 495 ms 65008 KB Output is correct
4 Correct 25 ms 65060 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 25 ms 65032 KB Output is correct
7 Correct 1058 ms 112296 KB Output is correct
8 Correct 1041 ms 120952 KB Output is correct
9 Correct 1004 ms 125564 KB Output is correct
10 Correct 1148 ms 143512 KB Output is correct
11 Correct 1144 ms 143552 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1010 ms 126156 KB Output is correct
14 Correct 502 ms 155904 KB Output is correct
15 Correct 1065 ms 126284 KB Output is correct
16 Correct 1158 ms 143048 KB Output is correct
17 Correct 1352 ms 127260 KB Output is correct
18 Correct 1254 ms 127180 KB Output is correct
19 Correct 1271 ms 144256 KB Output is correct
20 Correct 1227 ms 128156 KB Output is correct
21 Correct 1377 ms 144812 KB Output is correct
22 Correct 1370 ms 145028 KB Output is correct
23 Correct 1255 ms 126680 KB Output is correct
24 Correct 717 ms 155076 KB Output is correct
25 Correct 1274 ms 123528 KB Output is correct
26 Correct 1358 ms 136916 KB Output is correct
27 Correct 5157 ms 118408 KB Output is correct
28 Correct 4599 ms 116332 KB Output is correct
29 Correct 4980 ms 124376 KB Output is correct
30 Correct 4595 ms 159564 KB Output is correct
31 Correct 5104 ms 187460 KB Output is correct
32 Correct 5117 ms 186624 KB Output is correct
33 Correct 842 ms 200384 KB Output is correct
34 Correct 5109 ms 157516 KB Output is correct
35 Correct 5144 ms 187484 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 64976 KB Output is correct
2 Correct 42 ms 65068 KB Output is correct
3 Correct 495 ms 65008 KB Output is correct
4 Correct 25 ms 65060 KB Output is correct
5 Correct 26 ms 64980 KB Output is correct
6 Correct 25 ms 65032 KB Output is correct
7 Correct 1058 ms 112296 KB Output is correct
8 Correct 1041 ms 120952 KB Output is correct
9 Correct 1004 ms 125564 KB Output is correct
10 Correct 1148 ms 143512 KB Output is correct
11 Correct 1144 ms 143552 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1010 ms 126156 KB Output is correct
14 Correct 502 ms 155904 KB Output is correct
15 Correct 1065 ms 126284 KB Output is correct
16 Correct 1158 ms 143048 KB Output is correct
17 Correct 1352 ms 127260 KB Output is correct
18 Correct 1254 ms 127180 KB Output is correct
19 Correct 1271 ms 144256 KB Output is correct
20 Correct 1227 ms 128156 KB Output is correct
21 Correct 1377 ms 144812 KB Output is correct
22 Correct 1370 ms 145028 KB Output is correct
23 Correct 1255 ms 126680 KB Output is correct
24 Correct 717 ms 155076 KB Output is correct
25 Correct 1274 ms 123528 KB Output is correct
26 Correct 1358 ms 136916 KB Output is correct
27 Correct 5157 ms 118408 KB Output is correct
28 Correct 4599 ms 116332 KB Output is correct
29 Correct 4980 ms 124376 KB Output is correct
30 Correct 4595 ms 159564 KB Output is correct
31 Correct 5104 ms 187460 KB Output is correct
32 Correct 5117 ms 186624 KB Output is correct
33 Correct 842 ms 200384 KB Output is correct
34 Correct 5109 ms 157516 KB Output is correct
35 Correct 5144 ms 187484 KB Output is correct
36 Execution timed out 9064 ms 157664 KB Time limit exceeded
37 Halted 0 ms 0 KB -