제출 #899382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899382		box	Escape Route (JOI21_escape_route)	C++17	70 / 100	9068 ms	198672 KiB

escape_route

#pragma GCC optimize("Ofast")
#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;
    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);
    static vi at_v[MAXN];
    for (int i = 0; i < Q; i++) {
        i64 x = INF;
        for (int j = 0; j < N; j++) if (T[i] <= end[j][U[i]]) x = min(x, S - T[i] + dist[j][V[i]]);
        ans[i] = x;
        if (dist[U[i]][V[i]] <= S) at_v[U[i]].push_back(i);
    }
    for (int src = 0; src < N; src++) {
        static i64 dist[MAXN];
        static bool consider[MAXN];
        fill(dist, dist + N, INF);
        fill(consider, consider + N, false);
        auto upd = [&](int i, i64 d) {
            if (dist[i] > d) {
                dist[i] = d;
                consider[i] = 1;
            }
        };
        i64 START = INF;
        priority_queue<pair<i64, pi>> edges;
        auto relax = [&]() {
            while (1) {
                int i = -1;
                for (int j = 0; j < N; j++) if (consider[j] && (i == -1 || dist[j] < dist[i])) i = j;
                if (i == -1) return;
                consider[i] = 0;
                for (int h : adj[i]) {
                    int j = i ^ A[h] ^ B[h];
                    if (dist[j] <= dist[i] + L[h]) continue;
                    if (START + dist[i] + L[h] <= C[h]) upd(j, dist[i] + L[h]);
                    else edges.push({C[h] - dist[i] - L[h], {i, h}});
                }
            }
        };
        upd(src, 0);
        sort(all(at_v[src]), [&](int i, int j) {
            return T[i] > T[j];
        });
        for (int i : at_v[src]) {
            START = T[i];
            while (sz(edges) && edges.top().first >= START) {
                auto [i, h] = edges.top().second; edges.pop();
                int j = i ^ A[h] ^ B[h];
                upd(j, dist[i] + L[h]);
            }
            relax();
            ans[i] = min(ans[i], dist[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: 0 / 30