oj.uz

Submission #935661

# Submission time Handle Problem Language Result Execution time Memory
935661 2024-02-29T10:46:40 Z Pannda Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 236908 KB 
#include "escape_route.h"

#include <bits/stdc++.h>
using namespace std;

vector<long long> calculate_necessary_time(int n, int m, long long S, int q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, vector<int> U, vector<int> V, vector<long long> T) {
    const long long INF = 4e18;

    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u = A[i];
        int v = B[i];
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    auto [f, g] = [&]() -> pair<vector<vector<vector<long long>>>, vector<vector<long long>>> {
        vector<vector<vector<long long>>> f(n);
        vector<vector<long long>> g(n);
        for (int source = 0; source < n; source++) {
            long long t = 0;
            while (true) {
                priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
                vector<long long> dist(n, INF);
                vector<int> par(n, -1);
                dist[source] = 0;
                pq.push({dist[source], source});
                while (!pq.empty()) {
                    auto [d, u] = pq.top();
                    pq.pop();
                    if (d != dist[u]) continue;
                    for (auto [v, i] : adj[u]) {
                        if (t + dist[u] > C[i] - L[i]) continue;
                        if (dist[u] + L[i] < dist[v]) {
                            dist[v] = dist[u] + L[i];
                            par[v] = i;
                            pq.push({dist[v], v});
                        }
                    }
                }
                f[source].push_back(dist);
                g[source].push_back(t);
                long long new_t = INF;
                for (int u = 0; u < n; u++) {
                    if (par[u] == -1) continue;
                    new_t = min(new_t, C[par[u]] - dist[u] + 1);
                }
                if (new_t >= S || new_t == t) break;
                t = new_t;
            }
        }
        return make_pair(f, g);
    }();

    vector<vector<long long>> dist = [&]() -> vector<vector<long long>> {
        vector<vector<long long>> dist(n, vector<long long>(n, INF));
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (f[u][0][v] != INF) {
                    dist[u][v] = S;
                }
            }
        }
        for (int u = 0; u < n; u++) {
            dist[u][u] = 0;
        }
        for (int w = 0; w < n; w++) {
            for (int u = 0; u < n; u++) {
                for (int v = 0; v < n; v++) {
                    dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v]);
                }
            }
        }
        vector<vector<long long>> true_dist = dist;
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                for (int w = 0; w < n; w++) {
                    if (f[w][0][v] != INF) {
                        true_dist[u][v] = min(true_dist[u][v], dist[u][w] + f[w][0][v]);
                    }
                }
            }
        }
        return true_dist;
    }();

    return [&]() -> vector<long long> {
        auto get = [&](int u, int v, long long t) -> long long {
            int i = upper_bound(g[u].begin(), g[u].end(), t) - g[u].begin() - 1;
            if (f[u][i][v] != INF) {
                return f[u][i][v];
            }
            long long res = INF;
            for (int w = 0; w < n; w++) {
                if (f[u][i][w] != INF) {
                    res = min(res, S - t + dist[w][v]);
                }
            }
            return res;
        };
        vector<long long> res(q);
        for (int i = 0; i < q; i++) {
            res[i] = get(U[i], V[i], T[i]);
        }
        return res;
    }();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 65112 KB Output is correct
2 Correct 14 ms 65192 KB Output is correct
3 Correct 52 ms 65116 KB Output is correct
4 Correct 9 ms 65192 KB Output is correct
5 Correct 10 ms 65172 KB Output is correct
6 Correct 10 ms 65112 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 123976 KB Output is correct
2 Correct 653 ms 180264 KB Output is correct
3 Correct 305 ms 145848 KB Output is correct
4 Correct 737 ms 187936 KB Output is correct
5 Correct 737 ms 172648 KB Output is correct
6 Correct 10 ms 65112 KB Output is correct
7 Correct 302 ms 156000 KB Output is correct
8 Correct 309 ms 194324 KB Output is correct
9 Correct 497 ms 155532 KB Output is correct
10 Correct 753 ms 202100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 65112 KB Output is correct
2 Correct 14 ms 65192 KB Output is correct
3 Correct 52 ms 65116 KB Output is correct
4 Correct 9 ms 65192 KB Output is correct
5 Correct 10 ms 65172 KB Output is correct
6 Correct 10 ms 65112 KB Output is correct
7 Correct 602 ms 123976 KB Output is correct
8 Correct 653 ms 180264 KB Output is correct
9 Correct 305 ms 145848 KB Output is correct
10 Correct 737 ms 187936 KB Output is correct
11 Correct 737 ms 172648 KB Output is correct
12 Correct 10 ms 65112 KB Output is correct
13 Correct 302 ms 156000 KB Output is correct
14 Correct 309 ms 194324 KB Output is correct
15 Correct 497 ms 155532 KB Output is correct
16 Correct 753 ms 202100 KB Output is correct
17 Correct 568 ms 168148 KB Output is correct
18 Correct 669 ms 169356 KB Output is correct
19 Correct 678 ms 195588 KB Output is correct
20 Correct 403 ms 158240 KB Output is correct
21 Correct 861 ms 204916 KB Output is correct
22 Correct 842 ms 204912 KB Output is correct
23 Correct 343 ms 157412 KB Output is correct
24 Correct 408 ms 196568 KB Output is correct
25 Correct 555 ms 157236 KB Output is correct
26 Correct 849 ms 205328 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 65112 KB Output is correct
2 Correct 14 ms 65192 KB Output is correct
3 Correct 52 ms 65116 KB Output is correct
4 Correct 9 ms 65192 KB Output is correct
5 Correct 10 ms 65172 KB Output is correct
6 Correct 10 ms 65112 KB Output is correct
7 Correct 602 ms 123976 KB Output is correct
8 Correct 653 ms 180264 KB Output is correct
9 Correct 305 ms 145848 KB Output is correct
10 Correct 737 ms 187936 KB Output is correct
11 Correct 737 ms 172648 KB Output is correct
12 Correct 10 ms 65112 KB Output is correct
13 Correct 302 ms 156000 KB Output is correct
14 Correct 309 ms 194324 KB Output is correct
15 Correct 497 ms 155532 KB Output is correct
16 Correct 753 ms 202100 KB Output is correct
17 Correct 568 ms 168148 KB Output is correct
18 Correct 669 ms 169356 KB Output is correct
19 Correct 678 ms 195588 KB Output is correct
20 Correct 403 ms 158240 KB Output is correct
21 Correct 861 ms 204916 KB Output is correct
22 Correct 842 ms 204912 KB Output is correct
23 Correct 343 ms 157412 KB Output is correct
24 Correct 408 ms 196568 KB Output is correct
25 Correct 555 ms 157236 KB Output is correct
26 Correct 849 ms 205328 KB Output is correct
27 Correct 2013 ms 166732 KB Output is correct
28 Correct 2631 ms 176072 KB Output is correct
29 Correct 3186 ms 200944 KB Output is correct
30 Correct 553 ms 156796 KB Output is correct
31 Correct 3434 ms 209740 KB Output is correct
32 Correct 3406 ms 209812 KB Output is correct
33 Correct 434 ms 197296 KB Output is correct
34 Correct 1932 ms 160076 KB Output is correct
35 Correct 3205 ms 206388 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 65112 KB Output is correct
2 Correct 14 ms 65192 KB Output is correct
3 Correct 52 ms 65116 KB Output is correct
4 Correct 9 ms 65192 KB Output is correct
5 Correct 10 ms 65172 KB Output is correct
6 Correct 10 ms 65112 KB Output is correct
7 Correct 602 ms 123976 KB Output is correct
8 Correct 653 ms 180264 KB Output is correct
9 Correct 305 ms 145848 KB Output is correct
10 Correct 737 ms 187936 KB Output is correct
11 Correct 737 ms 172648 KB Output is correct
12 Correct 10 ms 65112 KB Output is correct
13 Correct 302 ms 156000 KB Output is correct
14 Correct 309 ms 194324 KB Output is correct
15 Correct 497 ms 155532 KB Output is correct
16 Correct 753 ms 202100 KB Output is correct
17 Correct 568 ms 168148 KB Output is correct
18 Correct 669 ms 169356 KB Output is correct
19 Correct 678 ms 195588 KB Output is correct
20 Correct 403 ms 158240 KB Output is correct
21 Correct 861 ms 204916 KB Output is correct
22 Correct 842 ms 204912 KB Output is correct
23 Correct 343 ms 157412 KB Output is correct
24 Correct 408 ms 196568 KB Output is correct
25 Correct 555 ms 157236 KB Output is correct
26 Correct 849 ms 205328 KB Output is correct
27 Correct 2013 ms 166732 KB Output is correct
28 Correct 2631 ms 176072 KB Output is correct
29 Correct 3186 ms 200944 KB Output is correct
30 Correct 553 ms 156796 KB Output is correct
31 Correct 3434 ms 209740 KB Output is correct
32 Correct 3406 ms 209812 KB Output is correct
33 Correct 434 ms 197296 KB Output is correct
34 Correct 1932 ms 160076 KB Output is correct
35 Correct 3205 ms 206388 KB Output is correct
36 Execution timed out 9075 ms 236908 KB Time limit exceeded
37 Halted 0 ms 0 KB -