Submission #935675

#	Time	Username	Problem	Language	Result	Execution time	Memory
935675		Pannda	Escape Route (JOI21_escape_route)	C++17	70 / 100	9075 ms	234180 KiB

escape_route

#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> {
        vector<vector<vector<long long>>> memorize(n);
        for (int u = 0; u < n; u++) {
            memorize[u].resize(f[u].size(), vector<long long>(n, -1));
        }
        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];
            }
            if (memorize[u][i][v] == -1) {
                memorize[u][i][v] = INF;
                for (int w = 0; w < n; w++) {
                    if (f[u][i][w] != INF) {
                        memorize[u][i][v] = min(memorize[u][i][v],dist[w][v]);
                    }
                }
            }
            return memorize[u][i][v] + S - t;
        };
        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 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30