Submission #1157523

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157523		antonn	Escape Route (JOI21_escape_route)	C++20	100 / 100	2029 ms	426092 KiB

escape_route

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 90 + 7;
const ll inf = 1e18;

int n;
vector<array<ll, 4>> g[N];
ll zero_delay[N][N], f[N * N][N][N];
vector<int> qs[N];

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) {
    for (int i = 0; i < M; ++i) {
        g[A[i]].push_back({B[i], L[i], C[i], i});
        g[B[i]].push_back({A[i], L[i], C[i], i});
    }
    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            zero_delay[u][v] = inf;
        }
        vector<bool> vis(N);
        priority_queue<pair<ll, int>> pq;
        pq.push({0, u});
        zero_delay[u][u] = 0;
        while (!pq.empty()) {
            int x = pq.top().second;
            pq.pop();
            if (vis[x]) continue;
            vis[x] = 1;
            for (auto [v, l, c, id] : g[x]) {
                ll cost = zero_delay[u][x] + l;
                if (zero_delay[u][x] % S + l > c) {
                    cost += S - zero_delay[u][x] % S;
                }
                if (cost < zero_delay[u][v]) {
                    zero_delay[u][v] = cost;
                    pq.push({-zero_delay[u][v], v});
                } 
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        for (int u = 0; u < N; ++u) {
            for (int v = 0; v < N; ++v) {
                f[i][u][v] = inf;
            }
            if (A[i] != u && B[i] != u) continue;
            vector<bool> vis(N, 0);
            f[i][u][u] = C[i] - L[i];
            priority_queue<pair<ll, int>> pq;
            pq.push({0, u});
            while (!pq.empty()) {
                int x = pq.top().second;
                pq.pop();
                if (vis[x]) continue;
                vis[x] = 1;
                for (auto [v, l, c, id] : g[x]) {
                    ll cost = f[i][u][x] + l;
                    if (f[i][u][x] % S + l > c) {
                        cost += S - f[i][u][x] % S;
                    }
                    if (cost < f[i][u][v]) {
                        f[i][u][v] = cost;
                        pq.push({-f[i][u][v], v});
                    }
                }
            }
            for (int v = 0; v < N; ++v) {
                if (f[i][u][v] <= S) {
                    f[i][u][v] -= (C[i] - L[i]);
                } else {
                    f[i][u][v] = inf;
                }
            }
        }
    }
    
    vector<ll> sol(Q, inf);
    for (int i = 0; i < Q; ++i) {
        qs[U[i]].push_back(i);
        sol[i] = (T[i] == 0 ? 0 : S - T[i]) + zero_delay[U[i]][V[i]];
    }
    for (int u = 0; u < N; ++u) {
        sort(g[u].begin(), g[u].end(), [&](array<ll, 4> a, array<ll, 4> b) {
            return a[2] - a[1] > b[2] - b[1];
        });
    }
    for (int u = 0; u < N; ++u) {
        sort(qs[u].begin(), qs[u].end(), [&](int x, int y) {
            return T[x] > T[y];
        });
        vector<int> ind(N, 0);
        vector<ll> dist(N, inf);
        dist[u] = 0;
        int ptr = 0;
        while (true) {
            int who = -1;
            ll best = -inf;
            for (int x = 0; x < N; ++x) {
                if (ind[x] == g[x].size()) continue;
                if (g[x][ind[x]][2] - g[x][ind[x]][1] - dist[x] >= best) {
                    best = g[x][ind[x]][2] - g[x][ind[x]][1] - dist[x];
                    who = x;
                }
            }
            while (ptr < qs[u].size() && T[qs[u][ptr]] > best) {
                int id = qs[u][ptr];
                ll ans = inf;
                ans = min(ans, dist[V[id]]);
                for (int v = 0; v < N; ++v) {
                    if (dist[v] < inf) {
                        ans = min(ans, S - T[id] + zero_delay[v][V[id]]);
                    }
                }
                sol[id] = min(sol[id], ans);
                ++ptr;
            }
            if (best < 0) break;
            int id = g[who][ind[who]][3];
            int to = g[who][ind[who]][0];
            ++ind[who];
            for (int v = 0; v < N; ++v) {
                if (f[id][who][v] + dist[who] < dist[v]) {
                    dist[v] = f[id][who][v] + dist[who];
                }
            }
        }
    }
    return sol;
}

/**
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N, M, S, Q;
    cin >> N >> M >> S >> Q;
    vector<int> A(M), B(M), U(Q), V(Q);
    vector<ll> L(M), C(M), T(Q);
    for (int i = 0; i < M; ++i) cin >> A[i] >> B[i] >> L[i] >> C[i];
    for (int i = 0; i < Q; ++i) cin >> U[i] >> V[i] >> T[i];
    
    vector<ll> sol = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
    for (int i = 0; i < sol.size(); ++i) cout << sol[i] << "\n";
    return 0;
}
**/

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