oj.uz

Submission #899379

# Submission time Handle Problem Language Result Execution time Memory
899379 2024-01-06T00:38:56 Z box Escape Route (JOI21_escape_route) C++17
20 / 100
 1253 ms 135668 KB 
#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 <= 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];
                assert(START + dist[i] + L[h] <= C[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Incorrect 11 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1127 ms 120284 KB Output is correct
2 Correct 1209 ms 133656 KB Output is correct
3 Correct 1141 ms 125908 KB Output is correct
4 Correct 1195 ms 135668 KB Output is correct
5 Correct 1208 ms 134436 KB Output is correct
6 Correct 9 ms 65116 KB Output is correct
7 Correct 1125 ms 123096 KB Output is correct
8 Correct 294 ms 134208 KB Output is correct
9 Correct 1128 ms 111964 KB Output is correct
10 Correct 1253 ms 133612 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Incorrect 11 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Incorrect 11 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 65116 KB Output is correct
2 Incorrect 11 ms 65116 KB Output isn't correct
3 Halted 0 ms 0 KB -