Submission #1157495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157495		antonn	Escape Route (JOI21_escape_route)	C++20	0 / 100	9092 ms	112308 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, 3>> g[N];
ll zero_delay[N][N], dist[N][N], d[N];
bool vis[N];
vector<array<ll, 3>> intervals[N][N];

ll get_dist(int src, int dest, ll t) {
    for (int j = 0; j < N; ++j) {
        d[j] = inf;
        vis[j] = 0;
    }
    d[src] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u] == 1) continue;
        vis[u] = 1;
        for (auto [v, l, c] : g[u]) {
            if (t + d[u] + l <= c && d[u] + l < d[v]) {
                d[v] = d[u] + l;
                pq.push({-d[v], v});
            }
        }
    }
    return d[dest];
}

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]});
        g[B[i]].push_back({A[i], L[i], C[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] : g[x]) {
                if (zero_delay[u][x] + l <= c && zero_delay[u][x] + l <= zero_delay[u][v]) {
                    zero_delay[u][v] = zero_delay[u][x] + l;
                    pq.push({-zero_delay[u][v], v});
                } 
            }
        }
    }
    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            dist[u][v] = zero_delay[u][v];
        }
    }
    for (int step = 0; step < 100; ++step) {
        for (int w = 0; w < N; ++w) {
            for (int u = 0; u < N; ++u) {
                for (int v = 0; v < N; ++v) {
                    dist[u][v] = min(dist[u][v], dist[u][w] + S - dist[u][w] % S + dist[w][v]);
                }
            }
        }
    }

    int sum = 0;
    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            ll l = 0;
            while (l <= S) {
                ll d = get_dist(u, v, l);
                if (d == inf) break;
                ll low = l, high = S, sol = 0;
                while (low <= high) {
                    int mid = (low + high) / 2;
                    if (get_dist(u, v, mid) == d) {
                        sol = mid;
                        low = mid + 1;
                    } else {
                        high = mid - 1;
                    }
                }
                intervals[u][v].push_back({l, sol, d});
                l = sol + 1;
            }
            sum += intervals[u][v].size();
        }
    }

    vector<ll> sol(Q);
    for (int i = 0; i < Q; ++i) {
        ll ans = inf;
        for (int w = 0; w < N; ++w) {
            for (auto [l, r, x] : intervals[U[i]][w]) {
                if (l <= T[i] && T[i] <= r) {
                    if (w == V[i]) {
                        ans = min(ans, x);
                    } else {
                        ans = min(ans, S - T[i] + dist[w][V[i]]);
                    }
                }
            }
        }
        sol[i] = ans;
    }
    return sol;
}

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