oj.uz

Submission #935647

# Submission time Handle Problem Language Result Execution time Memory
935647 2024-02-29T10:20:16 Z Pannda Escape Route (JOI21_escape_route) C++17
0 / 100
 775 ms 202580 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 = 9e18;

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 65116 KB Output is correct
2 Incorrect 14 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 166704 KB Output is correct
2 Correct 639 ms 193196 KB Output is correct
3 Correct 340 ms 155828 KB Output is correct
4 Correct 771 ms 202580 KB Output is correct
5 Correct 775 ms 202068 KB Output is correct
6 Incorrect 9 ms 65116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 65116 KB Output is correct
2 Incorrect 14 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 65116 KB Output is correct
2 Incorrect 14 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 65116 KB Output is correct
2 Incorrect 14 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -