oj.uz

Submission #723453

# Submission time Handle Problem Language Result Execution time Memory
723453 2023-04-13T20:15:35 Z piOOE Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 147292 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)), dto(n, vector<ll>(n));

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

    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:127: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]
  127 |             if (k < dp.size()) {
      |                 ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65040 KB Output is correct
2 Correct 45 ms 64964 KB Output is correct
3 Correct 501 ms 65064 KB Output is correct
4 Correct 30 ms 64972 KB Output is correct
5 Correct 29 ms 65008 KB Output is correct
6 Correct 29 ms 65012 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1153 ms 114692 KB Output is correct
2 Correct 1120 ms 123564 KB Output is correct
3 Correct 1036 ms 114864 KB Output is correct
4 Correct 1196 ms 123240 KB Output is correct
5 Correct 1193 ms 123212 KB Output is correct
6 Correct 34 ms 64960 KB Output is correct
7 Correct 1074 ms 114776 KB Output is correct
8 Correct 540 ms 135556 KB Output is correct
9 Correct 1079 ms 114676 KB Output is correct
10 Correct 1177 ms 122856 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65040 KB Output is correct
2 Correct 45 ms 64964 KB Output is correct
3 Correct 501 ms 65064 KB Output is correct
4 Correct 30 ms 64972 KB Output is correct
5 Correct 29 ms 65008 KB Output is correct
6 Correct 29 ms 65012 KB Output is correct
7 Correct 1153 ms 114692 KB Output is correct
8 Correct 1120 ms 123564 KB Output is correct
9 Correct 1036 ms 114864 KB Output is correct
10 Correct 1196 ms 123240 KB Output is correct
11 Correct 1193 ms 123212 KB Output is correct
12 Correct 34 ms 64960 KB Output is correct
13 Correct 1074 ms 114776 KB Output is correct
14 Correct 540 ms 135556 KB Output is correct
15 Correct 1079 ms 114676 KB Output is correct
16 Correct 1177 ms 122856 KB Output is correct
17 Correct 1377 ms 114776 KB Output is correct
18 Correct 1322 ms 114780 KB Output is correct
19 Correct 1315 ms 125792 KB Output is correct
20 Correct 1238 ms 116048 KB Output is correct
21 Correct 1400 ms 123908 KB Output is correct
22 Correct 1388 ms 123992 KB Output is correct
23 Correct 1296 ms 114652 KB Output is correct
24 Correct 781 ms 137416 KB Output is correct
25 Correct 1298 ms 114656 KB Output is correct
26 Correct 1428 ms 125944 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65040 KB Output is correct
2 Correct 45 ms 64964 KB Output is correct
3 Correct 501 ms 65064 KB Output is correct
4 Correct 30 ms 64972 KB Output is correct
5 Correct 29 ms 65008 KB Output is correct
6 Correct 29 ms 65012 KB Output is correct
7 Correct 1153 ms 114692 KB Output is correct
8 Correct 1120 ms 123564 KB Output is correct
9 Correct 1036 ms 114864 KB Output is correct
10 Correct 1196 ms 123240 KB Output is correct
11 Correct 1193 ms 123212 KB Output is correct
12 Correct 34 ms 64960 KB Output is correct
13 Correct 1074 ms 114776 KB Output is correct
14 Correct 540 ms 135556 KB Output is correct
15 Correct 1079 ms 114676 KB Output is correct
16 Correct 1177 ms 122856 KB Output is correct
17 Correct 1377 ms 114776 KB Output is correct
18 Correct 1322 ms 114780 KB Output is correct
19 Correct 1315 ms 125792 KB Output is correct
20 Correct 1238 ms 116048 KB Output is correct
21 Correct 1400 ms 123908 KB Output is correct
22 Correct 1388 ms 123992 KB Output is correct
23 Correct 1296 ms 114652 KB Output is correct
24 Correct 781 ms 137416 KB Output is correct
25 Correct 1298 ms 114656 KB Output is correct
26 Correct 1428 ms 125944 KB Output is correct
27 Correct 5249 ms 115044 KB Output is correct
28 Correct 4756 ms 115200 KB Output is correct
29 Correct 5153 ms 124328 KB Output is correct
30 Correct 4590 ms 121412 KB Output is correct
31 Correct 5261 ms 132308 KB Output is correct
32 Correct 5228 ms 131860 KB Output is correct
33 Correct 892 ms 147292 KB Output is correct
34 Correct 5186 ms 119460 KB Output is correct
35 Correct 5154 ms 134484 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65040 KB Output is correct
2 Correct 45 ms 64964 KB Output is correct
3 Correct 501 ms 65064 KB Output is correct
4 Correct 30 ms 64972 KB Output is correct
5 Correct 29 ms 65008 KB Output is correct
6 Correct 29 ms 65012 KB Output is correct
7 Correct 1153 ms 114692 KB Output is correct
8 Correct 1120 ms 123564 KB Output is correct
9 Correct 1036 ms 114864 KB Output is correct
10 Correct 1196 ms 123240 KB Output is correct
11 Correct 1193 ms 123212 KB Output is correct
12 Correct 34 ms 64960 KB Output is correct
13 Correct 1074 ms 114776 KB Output is correct
14 Correct 540 ms 135556 KB Output is correct
15 Correct 1079 ms 114676 KB Output is correct
16 Correct 1177 ms 122856 KB Output is correct
17 Correct 1377 ms 114776 KB Output is correct
18 Correct 1322 ms 114780 KB Output is correct
19 Correct 1315 ms 125792 KB Output is correct
20 Correct 1238 ms 116048 KB Output is correct
21 Correct 1400 ms 123908 KB Output is correct
22 Correct 1388 ms 123992 KB Output is correct
23 Correct 1296 ms 114652 KB Output is correct
24 Correct 781 ms 137416 KB Output is correct
25 Correct 1298 ms 114656 KB Output is correct
26 Correct 1428 ms 125944 KB Output is correct
27 Correct 5249 ms 115044 KB Output is correct
28 Correct 4756 ms 115200 KB Output is correct
29 Correct 5153 ms 124328 KB Output is correct
30 Correct 4590 ms 121412 KB Output is correct
31 Correct 5261 ms 132308 KB Output is correct
32 Correct 5228 ms 131860 KB Output is correct
33 Correct 892 ms 147292 KB Output is correct
34 Correct 5186 ms 119460 KB Output is correct
35 Correct 5154 ms 134484 KB Output is correct
36 Execution timed out 9043 ms 119448 KB Time limit exceeded
37 Halted 0 ms 0 KB -