oj.uz

Submission #723933

# Submission time Handle Problem Language Result Execution time Memory
723933 2023-04-14T13:25:49 Z piOOE Escape Route (JOI21_escape_route) C++17
100 / 100
 2617 ms 177520 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);
    }

    A.resize(2 * m), B.resize(2 * m), L.resize(2 * m), C.resize(2 * m);
    
    for (int i = 0; i < m; ++i) {
        A[i + m] = B[i], B[i + m] = A[i];
        C[i + m] = C[i], L[i + m] = L[i];
    }
    
    m *= 2;

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

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

    auto dijkstra = [&](int source, ll s) -> vector<ll> {
        vector<ll> dist(n, 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 || dist[i] < dist[v])) {
                    v = i;
                }
            }

            used[v] = true;

            for (int i : adj[v]) {
                int to = B[i];
                ll d = L[i] + (dist[v] % S <= C[i] - L[i] ? dist[v] : (dist[v] / S + 1) * S);
                if (dist[to] > d) {
                    dist[to] = d;
                }
            }
        }

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

        return dist;
    };

    vector dist0(n, vector<ll>(n));
    vector dp(m, vector<ll>(n));

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

    for (int e = 0; e < m; ++e) {
        dp[e] = dijkstra(A[e], C[e] - L[e]);
        for (int to = 0; to < n; ++to) {
            if (C[e] - L[e] + dp[e][to] >= S) {
                dp[e][to] = inf;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        sort(adj[i].begin(), adj[i].end(), [&](int x, int y) {
            return C[x] - L[x] > C[y] - L[y];
        });
    };

    for (int i = 0; i < n; ++i) {
        sort(queries[i].begin(), queries[i].end(), [&](int x, int y) {
            return T[x] > T[y];
        });
        int k = 0;

        vector<int> id(n);
        vector<ll> d(m, inf);
        d[i] = 0;

        while (true) {
            pair<ll, int> best{-1, -1};

            for (int x = 0; x < n; ++x) {
                if (id[x] < adj[x].size()) {
                    int e = adj[x][id[x]];
                    best = max(best, {C[e] - L[e] - d[x], x});
                }
            }

            while (k < queries[i].size() && T[queries[i][k]] > best.first) {
                int j = queries[i][k++];
                answer[j] = min(answer[j], d[V[j]]);
                for (int x = 0; x < n; ++x) {
                    if (T[j] + d[x] < S) {
                        answer[j] = min(answer[j], S - T[j] + dist0[x][V[j]]);
                    }
                }
            }

            if (best.first == -1) {
                break;
            }

            int x = best.second;
            int e = adj[x][id[x]++];

            for (int to = 0; to < n; ++to) {
                d[to] = min(d[to], d[x] + dp[e][to]);
            }
        }
    }

    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:99:27: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 if (id[x] < adj[x].size()) {
escape_route.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while (k < queries[i].size() && T[queries[i][k]] > best.first) {
      |                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 33 ms 64988 KB Output is correct
3 Correct 66 ms 64968 KB Output is correct
4 Correct 29 ms 64964 KB Output is correct
5 Correct 48 ms 64988 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 1563 ms 113404 KB Output is correct
2 Correct 1448 ms 121840 KB Output is correct
3 Correct 1411 ms 113496 KB Output is correct
4 Correct 1485 ms 122912 KB Output is correct
5 Correct 1457 ms 122448 KB Output is correct
6 Correct 24 ms 64980 KB Output is correct
7 Correct 1420 ms 113268 KB Output is correct
8 Correct 1563 ms 134388 KB Output is correct
9 Correct 1521 ms 123168 KB Output is correct
10 Correct 1577 ms 130580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 33 ms 64988 KB Output is correct
3 Correct 66 ms 64968 KB Output is correct
4 Correct 29 ms 64964 KB Output is correct
5 Correct 48 ms 64988 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 1563 ms 113404 KB Output is correct
8 Correct 1448 ms 121840 KB Output is correct
9 Correct 1411 ms 113496 KB Output is correct
10 Correct 1485 ms 122912 KB Output is correct
11 Correct 1457 ms 122448 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1420 ms 113268 KB Output is correct
14 Correct 1563 ms 134388 KB Output is correct
15 Correct 1521 ms 123168 KB Output is correct
16 Correct 1577 ms 130580 KB Output is correct
17 Correct 1326 ms 125496 KB Output is correct
18 Correct 1279 ms 124620 KB Output is correct
19 Correct 1363 ms 136100 KB Output is correct
20 Correct 1305 ms 123536 KB Output is correct
21 Correct 1381 ms 130536 KB Output is correct
22 Correct 1480 ms 130264 KB Output is correct
23 Correct 1371 ms 124900 KB Output is correct
24 Correct 1411 ms 144724 KB Output is correct
25 Correct 1340 ms 137836 KB Output is correct
26 Correct 1428 ms 134496 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 33 ms 64988 KB Output is correct
3 Correct 66 ms 64968 KB Output is correct
4 Correct 29 ms 64964 KB Output is correct
5 Correct 48 ms 64988 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 1563 ms 113404 KB Output is correct
8 Correct 1448 ms 121840 KB Output is correct
9 Correct 1411 ms 113496 KB Output is correct
10 Correct 1485 ms 122912 KB Output is correct
11 Correct 1457 ms 122448 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1420 ms 113268 KB Output is correct
14 Correct 1563 ms 134388 KB Output is correct
15 Correct 1521 ms 123168 KB Output is correct
16 Correct 1577 ms 130580 KB Output is correct
17 Correct 1326 ms 125496 KB Output is correct
18 Correct 1279 ms 124620 KB Output is correct
19 Correct 1363 ms 136100 KB Output is correct
20 Correct 1305 ms 123536 KB Output is correct
21 Correct 1381 ms 130536 KB Output is correct
22 Correct 1480 ms 130264 KB Output is correct
23 Correct 1371 ms 124900 KB Output is correct
24 Correct 1411 ms 144724 KB Output is correct
25 Correct 1340 ms 137836 KB Output is correct
26 Correct 1428 ms 134496 KB Output is correct
27 Correct 1536 ms 119112 KB Output is correct
28 Correct 1580 ms 119068 KB Output is correct
29 Correct 1588 ms 146244 KB Output is correct
30 Correct 1496 ms 129196 KB Output is correct
31 Correct 1622 ms 144864 KB Output is correct
32 Correct 1623 ms 145380 KB Output is correct
33 Correct 1255 ms 155144 KB Output is correct
34 Correct 1536 ms 125296 KB Output is correct
35 Correct 1600 ms 145148 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 33 ms 64988 KB Output is correct
3 Correct 66 ms 64968 KB Output is correct
4 Correct 29 ms 64964 KB Output is correct
5 Correct 48 ms 64988 KB Output is correct
6 Correct 31 ms 64980 KB Output is correct
7 Correct 1563 ms 113404 KB Output is correct
8 Correct 1448 ms 121840 KB Output is correct
9 Correct 1411 ms 113496 KB Output is correct
10 Correct 1485 ms 122912 KB Output is correct
11 Correct 1457 ms 122448 KB Output is correct
12 Correct 24 ms 64980 KB Output is correct
13 Correct 1420 ms 113268 KB Output is correct
14 Correct 1563 ms 134388 KB Output is correct
15 Correct 1521 ms 123168 KB Output is correct
16 Correct 1577 ms 130580 KB Output is correct
17 Correct 1326 ms 125496 KB Output is correct
18 Correct 1279 ms 124620 KB Output is correct
19 Correct 1363 ms 136100 KB Output is correct
20 Correct 1305 ms 123536 KB Output is correct
21 Correct 1381 ms 130536 KB Output is correct
22 Correct 1480 ms 130264 KB Output is correct
23 Correct 1371 ms 124900 KB Output is correct
24 Correct 1411 ms 144724 KB Output is correct
25 Correct 1340 ms 137836 KB Output is correct
26 Correct 1428 ms 134496 KB Output is correct
27 Correct 1536 ms 119112 KB Output is correct
28 Correct 1580 ms 119068 KB Output is correct
29 Correct 1588 ms 146244 KB Output is correct
30 Correct 1496 ms 129196 KB Output is correct
31 Correct 1622 ms 144864 KB Output is correct
32 Correct 1623 ms 145380 KB Output is correct
33 Correct 1255 ms 155144 KB Output is correct
34 Correct 1536 ms 125296 KB Output is correct
35 Correct 1600 ms 145148 KB Output is correct
36 Correct 2453 ms 130724 KB Output is correct
37 Correct 2617 ms 145924 KB Output is correct
38 Correct 2435 ms 149964 KB Output is correct
39 Correct 2563 ms 172168 KB Output is correct
40 Correct 2485 ms 172428 KB Output is correct
41 Correct 1386 ms 177520 KB Output is correct
42 Correct 2461 ms 136268 KB Output is correct
43 Correct 2486 ms 134120 KB Output is correct