Submission #1156846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156846		antonn	Escape Route (JOI21_escape_route)	C++20	5 / 100	9093 ms	111944 KiB

escape_route

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


const ll inf = 1e18;


struct aboba {
    ll time;
    ll extend;
    ll node;
};

bool operator < (aboba a, aboba b) {
    if (a.time == b.time) {
        return a.extend < b.extend;
    }
    return a.time > b.time;
}


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) {
    vector<vector<array<ll, 3>>> g(N);
    for (int i = 0; i < M; i += 1) {
        g[A[i]].push_back({B[i], L[i], C[i]});
        g[B[i]].push_back({A[i], L[i], C[i]});
    }
    vector<vector<vector<pair<ll, ll>>>> paths(N, vector<vector<pair<ll, ll>>>(N)); 
    vector<vector<ll>> zero_delay(N, vector<ll>(N, inf));
    for (int u = 0; u < N; u += 1) {
        priority_queue<aboba> pq;
        pq.push({0, -inf, u});
        paths[u][u].push_back({0, inf});
        vector<int> vis(N);
        while (!pq.empty()) {
            aboba x = pq.top();
            pq.pop();
            ll t = -x.time;
            ll e = -x.extend;
            int node = x.node;
            if (vis[node] > N * N) {
                break;
            }
            vis[node] += 1;
            for (auto [v, l, c] : g[node]) {
                ll could = c - (t + l);
                if (could < 0) {
                    continue;
                }
                bool bad = 0;
                for (auto [time, extend] : paths[u][v]) {
                    if (t + l >= time && min(e, could) <= extend) {
                        bad = 1;
                        break;
                    }
                }
                if (!bad) {
                    zero_delay[u][v] = min(zero_delay[u][v], t + l); 
                    paths[u][v].push_back({t + l, min(e, could)});
                    pq.push({-(t + l), -min(e, could), v});
                }
            }
        }
    }
    for (int u = 0; u < N; u += 1) {
        zero_delay[u][u] = 0;
    }
    
    vector<vector<ll>> dist(N, vector<ll>(N, inf));
    for (int u = 0; u < N; u += 1) {
        for (int v = 0; v < N; v += 1) {
            if (zero_delay[u][v] <= S) {
                dist[u][v] = zero_delay[u][v];
            }
        }
    }
    for (int st = 0; st < 100; st += 1) {
        for (int w = 0; w < N; w += 1) {
            for (int u = 0; u < N; u += 1) {
                for (int v = 0; v < N; v += 1) {
                    dist[u][v] = min(dist[u][v], dist[u][w] + (dist[u][w] == 0 ? 0 : S - dist[u][w] % S) + zero_delay[w][v]);
                }
            }
        }
    }
    vector<ll> sol(Q);
    for (int i = 0; i < Q; i += 1) {
        ll ans = 1e18;
        ans = S - T[i] + dist[U[i]][V[i]];
        for (int w = 0; w < N; w += 1) {
            for (auto [time, extend] : paths[U[i]][w]) {
                if (extend >= T[i]) {
                    if (w == V[i]) {
                        ans = min(ans, time);
                    } else {
                        ans = min(ans, S - T[i] + dist[w][V[i]]);
                    }
                }
            }
        }
        sol[i] = ans;
    }
    return sol;
}

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