Submission #901957

#	Time	Username	Problem	Language	Result	Execution time	Memory
901957		box	Escape Route (JOI21_escape_route)	C++17	100 / 100	2269 ms	201896 KiB

escape_route

// #pragma GCC optimize("Ofast")
#ifndef LOCAL
#include "escape_route.h"
#endif
#include <bits/stdc++.h>
using namespace std;
 
#ifdef LOCAL
#define bug(x) cerr << "L" << __LINE__ << " | " << #x << " => " << x << endl
#else
#define bug(x)
#define cerr if (0) cerr
#endif
 
#define ar array
#define sz(v) int(std::size(v))
#define all(v) std::begin(v), std::end(v)
using i64 = long long;
using vi = vector<int>;
using pi = pair<int, int>;
 
vector<i64> calculate_necessary_time(int N, int M, i64 S, int Q, vi A, vi B, vector<i64> L, vector<i64> C, vi U, vi V, vector<i64> T)
{
    const int MAXN = 90, MAXM = MAXN*MAXN;
    const i64 INF = 1e18;
    static vi adj[MAXN];
    for (int i = 0; i < M; i++) adj[A[i]].push_back(i), adj[B[i]].push_back(i);
    static i64 dist[MAXN][MAXN], end[MAXN][MAXN];
    for (int src = 0; src < N; src++) {
        {
            fill(dist[src], dist[src] + N, INF);
            using X = pair<i64, int>;
            priority_queue<X, vector<X>, greater<X>> pq;
            auto ins = [&](int i, i64 d) {
                if (dist[src][i] > d)
                    pq.push({dist[src][i] = d, i});
            };
            ins(src, 0);
            while (sz(pq)) {
                auto [d, i] = pq.top(); pq.pop();
                if (dist[src][i] != d) continue;
                for (int h : adj[i]) ins(i ^ A[h] ^ B[h], L[h] + (d % S <= C[h] - L[h] ? d : (d / S + 1) * S));
            }
        }
        {
            fill(end[src], end[src] + N, -1);
            using X = pair<i64, int>;
            priority_queue<X> pq;
            auto ins = [&](int i, i64 d) {
                if (end[src][i] < d)
                    pq.push({end[src][i] = d, i});
            };
            ins(src, S);
            while (sz(pq)) {
                auto [d, i] = pq.top(); pq.pop();
                if (end[src][i] != d) continue;
                for (int h : adj[i]) ins(i ^ A[h] ^ B[h], min(C[h], d) - L[h]);
            }
        }
 
    }
    vector<i64> ans(Q, INF);
    for (int i = 0; i < Q; i++) for (int j = 0; j < N; j++) if (T[i] <= end[j][U[i]]) ans[i] = min(ans[i], S - T[i] + dist[j][V[i]]);
    static i64 one[MAXM][MAXN], two[MAXM][MAXN], mid[MAXM]; int E = 0;
    static bool vis[MAXN];
    vector<tuple<i64, int, int>> upd;
    for (int I = 0; I < N; I++) for (int H : adj[I]) {
        int J = I^A[H]^B[H];
        mid[E] = L[H];
        {
            fill(one[E], one[E]+N, INF);
            fill(vis, vis+N, 0);
            one[E][I] = 0;
            for (int rep = 0; rep < N; rep++) {
                int i = -1;
                for (int j = 0; j < N; j++) if (!vis[j] && one[E][j] < INF && (i == -1 || one[E][i] > one[E][j])) i = j;
                if (i == -1) break;
                vis[i] = 1;
                for (int h : adj[i]) {
                    int j = i^A[h]^B[h];
                    i64 T = C[H]-L[H]-one[E][i];
                    if (T <= C[h]) one[E][j] = min(one[E][j], one[E][i]+L[h]);
                }
            }
        }
        {
            fill(two[E], two[E]+N, INF);
            fill(vis, vis+N, 0);
            two[E][J] = 0;
            for (int rep = 0; rep < N; rep++) {
                int i = -1;
                for (int j = 0; j < N; j++) if (!vis[j] && two[E][j] < INF && (i == -1 || two[E][i] > two[E][j])) i = j;
                if (i == -1) break;
                vis[i] = 1;
                for (int h : adj[i]) {
                    int j = i^A[h]^B[h];
                    i64 T = two[E][i]+C[H];
                    if (T <= C[h]-L[h]) two[E][j] = min(two[E][j], two[E][i]+L[h]);
                }
            }
        }
        for (int x = 0; x < N; x++) if (one[E][x] < INF) {
            i64 T = C[H]-L[H]-one[E][x];
            // assert(T >= 0);
            upd.push_back({T, E, x});
        }
        E++;
    }
    vi perm(Q);
    iota(all(perm), 0);
    sort(all(perm), [&](int i, int j) {
        return T[i]>T[j];
    });
    sort(all(upd), greater<>());
    int p = 0;
    static i64 other[MAXN][MAXN];
    for (int i = 0; i < N; i++) fill(other[i], other[i]+N, INF);
    for (int i : perm) {
        while (p < sz(upd) && get<0>(upd[p]) >= T[i]) {
            auto [T, E, x] = upd[p++];
            for (int y = 0; y < N; y++) other[x][y] = min(other[x][y], one[E][x]+two[E][y]+mid[E]);
        }
        ans[i] = min(ans[i], other[U[i]][V[i]]);
    }
    return ans;
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M, Q; i64 S; cin >> N >> M >> S >> Q;
    vi A(M), B(M); vector<i64> L(M), C(M);
    for (int i = 0; i < M; i++) cin >> A[i] >> B[i] >> L[i] >> C[i];
    vi U(Q), V(Q); vector<i64> T(Q);
    for (int i = 0; i < Q; i++) cin >> U[i] >> V[i] >> T[i];
    auto ans = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
    assert(sz(ans) == Q);
    for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}
#endif

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