제출 #1125110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125110		Pannda	Escape Route (JOI21_escape_route)	C++17	70 / 100	9095 ms	190568 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 s = 0; s < n; s++) {
            long long t = 0;
            while (true) {
                vector<long long> dist(n, INF);
                vector<int> par(n, -1);
                vector<bool> popped(n, false);
                dist[s] = 0;
                while (true) {
                    int u = -1;
                    long long mn = INF;
                    for (int v = 0; v < n; v++) {
                        if (popped[v]) continue;
                        if (dist[v] < mn) {
                            u = v;
                            mn = dist[v];
                        }
                    }
                    if (u == -1) break;
                    popped[u] = true;
                    for (auto [v, i] : adj[u]) {
                        if (t + dist[u] + L[i] > C[i]) continue;
                        if (dist[u] + L[i] < dist[v]) {
                            dist[v] = dist[u] + L[i];
                            par[v] = i;
                        }
                    }
                }
                g[s].push_back(t);
                f[s].push_back(dist);
                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 (u == v) dist[u][v] = 0;
                else if (f[u][0][v] != INF) dist[u][v] = S;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int u = 0; u < n; u++) {
                for (int v = 0; v < n; v++) {
                    dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v]);
                }
            }
        }
        vector<vector<long long>> true_dist(n, vector<long long>(n, INF));
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                for (int w = 0; w < n; w++) {
                    true_dist[u][v] = min(true_dist[u][v], dist[u][w] + f[w][0][v]);
                }
            }
        }
        return true_dist;
    }();

    return [&]() -> vector<long long> {
        auto query = [&](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 ans = INF;
            for (int w = 0; w < n; w++) {
                if (f[u][i][w] != INF) {
                    ans = min(ans, S - t + dist[w][v]);
                }
            }
            return ans;
        };
        vector<long long> ans(q);
        for (int i = 0; i < q; i++) {
            ans[i] = query(U[i], V[i], T[i]);
        }
        return ans;
    }();
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30