oj.uz

Submission #723627

# Submission time Handle Problem Language Result Execution time Memory
723627 2023-04-14T06:34:03 Z piOOE Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 154800 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) {
    constexpr ll inf = 3e18;
    vector<ll> answer(q, inf);
    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);
    }

    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);
    }

    constexpr int X = 90;

    for (int i = 0; i < n; ++i) {

        if (queries[i].size() > X) {
            for (int j : queries[i]) {
                ll ans = inf;
                for (int mid = 0; mid < n; ++mid) {
                    ll dist = S - 1 - dto[mid][i] < T[j] ? inf : S - 1 - T[j] + 1 + from[mid][V[j]];
                    ans = min(ans, dist);
                }

                answer[j] = ans;
            }

            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]) {
                int k = lower_bound(till.begin(), till.end(), T[j]) - till.begin();
                if (k < dp.size()) {
                    answer[j] = min(answer[j], dp[k][V[j]]);
                }
            }
        } else {
            for (int j : queries[i]) {
                answer[j] = dijkstra(i, T[j])[V[j]];
            }
        }
    }

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64980 KB Output is correct
2 Correct 34 ms 64960 KB Output is correct
3 Correct 49 ms 65092 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 42 ms 64996 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 128264 KB Output is correct
2 Correct 632 ms 141192 KB Output is correct
3 Correct 750 ms 150528 KB Output is correct
4 Correct 878 ms 137248 KB Output is correct
5 Correct 834 ms 137548 KB Output is correct
6 Correct 29 ms 64988 KB Output is correct
7 Correct 713 ms 151748 KB Output is correct
8 Correct 591 ms 150124 KB Output is correct
9 Correct 647 ms 151148 KB Output is correct
10 Correct 776 ms 136948 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64980 KB Output is correct
2 Correct 34 ms 64960 KB Output is correct
3 Correct 49 ms 65092 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 42 ms 64996 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 653 ms 128264 KB Output is correct
8 Correct 632 ms 141192 KB Output is correct
9 Correct 750 ms 150528 KB Output is correct
10 Correct 878 ms 137248 KB Output is correct
11 Correct 834 ms 137548 KB Output is correct
12 Correct 29 ms 64988 KB Output is correct
13 Correct 713 ms 151748 KB Output is correct
14 Correct 591 ms 150124 KB Output is correct
15 Correct 647 ms 151148 KB Output is correct
16 Correct 776 ms 136948 KB Output is correct
17 Correct 1502 ms 150896 KB Output is correct
18 Correct 1452 ms 152616 KB Output is correct
19 Correct 1399 ms 139972 KB Output is correct
20 Correct 1398 ms 154800 KB Output is correct
21 Correct 1504 ms 138508 KB Output is correct
22 Correct 1558 ms 139140 KB Output is correct
23 Correct 1414 ms 152440 KB Output is correct
24 Correct 893 ms 154128 KB Output is correct
25 Correct 1452 ms 135632 KB Output is correct
26 Correct 1567 ms 152900 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64980 KB Output is correct
2 Correct 34 ms 64960 KB Output is correct
3 Correct 49 ms 65092 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 42 ms 64996 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 653 ms 128264 KB Output is correct
8 Correct 632 ms 141192 KB Output is correct
9 Correct 750 ms 150528 KB Output is correct
10 Correct 878 ms 137248 KB Output is correct
11 Correct 834 ms 137548 KB Output is correct
12 Correct 29 ms 64988 KB Output is correct
13 Correct 713 ms 151748 KB Output is correct
14 Correct 591 ms 150124 KB Output is correct
15 Correct 647 ms 151148 KB Output is correct
16 Correct 776 ms 136948 KB Output is correct
17 Correct 1502 ms 150896 KB Output is correct
18 Correct 1452 ms 152616 KB Output is correct
19 Correct 1399 ms 139972 KB Output is correct
20 Correct 1398 ms 154800 KB Output is correct
21 Correct 1504 ms 138508 KB Output is correct
22 Correct 1558 ms 139140 KB Output is correct
23 Correct 1414 ms 152440 KB Output is correct
24 Correct 893 ms 154128 KB Output is correct
25 Correct 1452 ms 135632 KB Output is correct
26 Correct 1567 ms 152900 KB Output is correct
27 Correct 5440 ms 130416 KB Output is correct
28 Correct 4821 ms 129776 KB Output is correct
29 Correct 5263 ms 141388 KB Output is correct
30 Correct 4785 ms 119836 KB Output is correct
31 Correct 5416 ms 130784 KB Output is correct
32 Correct 5445 ms 130104 KB Output is correct
33 Correct 1063 ms 143812 KB Output is correct
34 Correct 5408 ms 117740 KB Output is correct
35 Correct 5387 ms 130872 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64980 KB Output is correct
2 Correct 34 ms 64960 KB Output is correct
3 Correct 49 ms 65092 KB Output is correct
4 Correct 27 ms 65008 KB Output is correct
5 Correct 42 ms 64996 KB Output is correct
6 Correct 30 ms 64980 KB Output is correct
7 Correct 653 ms 128264 KB Output is correct
8 Correct 632 ms 141192 KB Output is correct
9 Correct 750 ms 150528 KB Output is correct
10 Correct 878 ms 137248 KB Output is correct
11 Correct 834 ms 137548 KB Output is correct
12 Correct 29 ms 64988 KB Output is correct
13 Correct 713 ms 151748 KB Output is correct
14 Correct 591 ms 150124 KB Output is correct
15 Correct 647 ms 151148 KB Output is correct
16 Correct 776 ms 136948 KB Output is correct
17 Correct 1502 ms 150896 KB Output is correct
18 Correct 1452 ms 152616 KB Output is correct
19 Correct 1399 ms 139972 KB Output is correct
20 Correct 1398 ms 154800 KB Output is correct
21 Correct 1504 ms 138508 KB Output is correct
22 Correct 1558 ms 139140 KB Output is correct
23 Correct 1414 ms 152440 KB Output is correct
24 Correct 893 ms 154128 KB Output is correct
25 Correct 1452 ms 135632 KB Output is correct
26 Correct 1567 ms 152900 KB Output is correct
27 Correct 5440 ms 130416 KB Output is correct
28 Correct 4821 ms 129776 KB Output is correct
29 Correct 5263 ms 141388 KB Output is correct
30 Correct 4785 ms 119836 KB Output is correct
31 Correct 5416 ms 130784 KB Output is correct
32 Correct 5445 ms 130104 KB Output is correct
33 Correct 1063 ms 143812 KB Output is correct
34 Correct 5408 ms 117740 KB Output is correct
35 Correct 5387 ms 130872 KB Output is correct
36 Execution timed out 9060 ms 118368 KB Time limit exceeded
37 Halted 0 ms 0 KB -