oj.uz

Submission #723632

# Submission time Handle Problem Language Result Execution time Memory
723632 2023-04-14T06:37:59 Z piOOE Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 138108 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);
    }

    for (int i = 0; i < n; ++i) {
        if (queries[i].size() > m) {
            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:70:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |         if (queries[i].size() > m) {
      |             ~~~~~~~~~~~~~~~~~~^~~
escape_route.cpp:123: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]
  123 |                 if (k < dp.size()) {
      |                     ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 39 ms 65012 KB Output is correct
3 Correct 44 ms 64972 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 38 ms 64980 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 112004 KB Output is correct
2 Correct 588 ms 120372 KB Output is correct
3 Correct 646 ms 112080 KB Output is correct
4 Correct 734 ms 121484 KB Output is correct
5 Correct 698 ms 121508 KB Output is correct
6 Correct 29 ms 64972 KB Output is correct
7 Correct 628 ms 111936 KB Output is correct
8 Correct 518 ms 133908 KB Output is correct
9 Correct 601 ms 112008 KB Output is correct
10 Correct 700 ms 121112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 39 ms 65012 KB Output is correct
3 Correct 44 ms 64972 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 38 ms 64980 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 641 ms 112004 KB Output is correct
8 Correct 588 ms 120372 KB Output is correct
9 Correct 646 ms 112080 KB Output is correct
10 Correct 734 ms 121484 KB Output is correct
11 Correct 698 ms 121508 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 628 ms 111936 KB Output is correct
14 Correct 518 ms 133908 KB Output is correct
15 Correct 601 ms 112008 KB Output is correct
16 Correct 700 ms 121112 KB Output is correct
17 Correct 1470 ms 112008 KB Output is correct
18 Correct 1415 ms 111948 KB Output is correct
19 Correct 1352 ms 124336 KB Output is correct
20 Correct 1464 ms 113152 KB Output is correct
21 Correct 1501 ms 122208 KB Output is correct
22 Correct 1510 ms 122304 KB Output is correct
23 Correct 1403 ms 112000 KB Output is correct
24 Correct 839 ms 135676 KB Output is correct
25 Correct 1439 ms 111948 KB Output is correct
26 Correct 1516 ms 123040 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 39 ms 65012 KB Output is correct
3 Correct 44 ms 64972 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 38 ms 64980 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 641 ms 112004 KB Output is correct
8 Correct 588 ms 120372 KB Output is correct
9 Correct 646 ms 112080 KB Output is correct
10 Correct 734 ms 121484 KB Output is correct
11 Correct 698 ms 121508 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 628 ms 111936 KB Output is correct
14 Correct 518 ms 133908 KB Output is correct
15 Correct 601 ms 112008 KB Output is correct
16 Correct 700 ms 121112 KB Output is correct
17 Correct 1470 ms 112008 KB Output is correct
18 Correct 1415 ms 111948 KB Output is correct
19 Correct 1352 ms 124336 KB Output is correct
20 Correct 1464 ms 113152 KB Output is correct
21 Correct 1501 ms 122208 KB Output is correct
22 Correct 1510 ms 122304 KB Output is correct
23 Correct 1403 ms 112000 KB Output is correct
24 Correct 839 ms 135676 KB Output is correct
25 Correct 1439 ms 111948 KB Output is correct
26 Correct 1516 ms 123040 KB Output is correct
27 Correct 5318 ms 111940 KB Output is correct
28 Correct 4835 ms 112004 KB Output is correct
29 Correct 5206 ms 121236 KB Output is correct
30 Correct 4725 ms 114644 KB Output is correct
31 Correct 5232 ms 124424 KB Output is correct
32 Correct 5317 ms 123976 KB Output is correct
33 Correct 998 ms 138108 KB Output is correct
34 Correct 5207 ms 111948 KB Output is correct
35 Correct 5247 ms 124880 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 39 ms 65012 KB Output is correct
3 Correct 44 ms 64972 KB Output is correct
4 Correct 27 ms 64972 KB Output is correct
5 Correct 38 ms 64980 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 641 ms 112004 KB Output is correct
8 Correct 588 ms 120372 KB Output is correct
9 Correct 646 ms 112080 KB Output is correct
10 Correct 734 ms 121484 KB Output is correct
11 Correct 698 ms 121508 KB Output is correct
12 Correct 29 ms 64972 KB Output is correct
13 Correct 628 ms 111936 KB Output is correct
14 Correct 518 ms 133908 KB Output is correct
15 Correct 601 ms 112008 KB Output is correct
16 Correct 700 ms 121112 KB Output is correct
17 Correct 1470 ms 112008 KB Output is correct
18 Correct 1415 ms 111948 KB Output is correct
19 Correct 1352 ms 124336 KB Output is correct
20 Correct 1464 ms 113152 KB Output is correct
21 Correct 1501 ms 122208 KB Output is correct
22 Correct 1510 ms 122304 KB Output is correct
23 Correct 1403 ms 112000 KB Output is correct
24 Correct 839 ms 135676 KB Output is correct
25 Correct 1439 ms 111948 KB Output is correct
26 Correct 1516 ms 123040 KB Output is correct
27 Correct 5318 ms 111940 KB Output is correct
28 Correct 4835 ms 112004 KB Output is correct
29 Correct 5206 ms 121236 KB Output is correct
30 Correct 4725 ms 114644 KB Output is correct
31 Correct 5232 ms 124424 KB Output is correct
32 Correct 5317 ms 123976 KB Output is correct
33 Correct 998 ms 138108 KB Output is correct
34 Correct 5207 ms 111948 KB Output is correct
35 Correct 5247 ms 124880 KB Output is correct
36 Execution timed out 9009 ms 112084 KB Time limit exceeded
37 Halted 0 ms 0 KB -