Submission #1171548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171548		OI_Account	Escape Route (JOI21_escape_route)	C++20	5 / 100	9077 ms	220112 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vii;
typedef vector<ll> vll;

const int N = 90;
const int M = N * N / 2;
const int S = 4000;
const int Q = 3'000'000;
const ll INF = 1'000'000'000'000'000'000;

int n, m, q;
ll l[M + 10], c[M + 10], s;
ll x[Q + 10], y[Q + 10], t[Q + 10], ans[Q + 10];
ll dis0[N + 10][N + 10], mxT[N + 10][N + 10];
ll dis[N + 10][S + 10][N + 10];
ll d[N + 10], tim[N + 10];
vector<ll> imp[N + 10];
vector<pair<int, int>> adj[N + 10];

void calcDisType1(int r, ll timSt) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    set<pair<ll, int>> st;
    st.insert({0, r});
    d[r] = 0;
    tim[r] = timSt;
    while (!st.empty()) {
        int u = st.begin() -> second;
        st.erase(st.begin());
        for (auto [v, e]: adj[u]) {
            ll newDis = d[v], newTim;
            if (tim[u] <= c[e]) {
                if (d[u] + l[e] < d[v]) {
                    newDis = d[u] + l[e];
                    newTim = tim[u] + l[e];
                }
            }
            else if (d[u] + s - tim[u] + l[e] < d[v]) {
                newDis = d[u] + s - tim[u] + l[e];
                newTim = l[e];
            }
            if (newDis < d[v]) {
                st.erase({d[v], v});
                d[v] = newDis;
                tim[v] = newTim;
                st.insert({d[v], v});
            }
        }
    }
}

void calcDisType2(int r, ll timSt) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    set<pair<ll, int>> st;
    st.insert({0, r});
    d[r] = 0;
    tim[r] = timSt;
    while (!st.empty()) {
        int u = st.begin() -> second;
        st.erase(st.begin());
        for (auto [v, e]: adj[u]) 
            if (tim[u] <= c[e] && d[u] + l[e] < d[v]) {
                st.erase({d[v], v});
                d[v] = d[u] + l[e];
                tim[v] = tim[u] + l[e];
                st.insert({d[v], v});
            }
    }
}

void calcDis0() {
    for (int i = 1; i <= n; i++) {
        calcDisType1(i, 0);
        for (int j = 1; j <= n; j++)
            dis0[i][j] = d[j];
    }
}

void calcDis(int u) {
    imp[u].push_back(0);
    calcDisType2(u, 0);
    for (int i = 1; i <= n; i++)
        dis[u][0][i] = d[i];
    int pnt = 0;
    while (true) {
        ll l = imp[u].back(), r = s;
        while (r - l > 1) {
            ll mid = (l + r) >> 1;
            calcDisType2(u, mid);
            bool ch = false;
            for (int v = 1; v <= n; v++) {
                if (d[v] != dis[u][pnt][v]) {
                    ch = true;
                    break;
                }
            }
            if (ch) {
                r = mid;
                for (int v = 1; v <= n; v++)
                    dis[u][pnt + 1][v] = d[v];
            }
            else
                l = mid;
        }
        if (r != s) {
            pnt++;
            imp[u].push_back(r);
        }
        else
            break;
    }
}

void calcDis() {
    for (int i = 1; i <= n; i++)
        calcDis(i);
}

void calcMxT() {
    for (int i = 1; i <= n; i++) {
        mxT[i][i] = s;
        for (int j = 1; j <= n; j++) 
            if (j != i) {
                mxT[i][j] = -1;
                for (int pnt = 0; pnt < (int) imp[i].size(); pnt++)
                    if (dis[i][pnt][j] != INF)
                        mxT[i][j] = (pnt + 1 == imp[i].size()? s - 1: imp[i][pnt + 1] - 1);
            }
    }   
}

void calcAns() {
    for (int i = 1; i <= q; i++) {
        int u = x[i], v = y[i];
        int idx = upper_bound(imp[u].begin(), imp[u].end(), t[i]) - imp[u].begin();
        ans[i] = dis[u][idx - 1][v];
        for (int mid = 1; mid <= n; mid++)
            if (t[i] <= mxT[u][mid])
                ans[i] = min(ans[i], s - t[i] + dis0[mid][v]);
    }
}

void solve() {
    calcDis0();
    calcDis();
    calcMxT();
    calcAns();
}

vll writeOutput() {
    vll res;
    for (int i = 1; i <= q; i++)
        res.push_back(ans[i]);
    return res;
}

vll calculate_necessary_time(int N, int M, ll S, int Q, vii A, vii B, vll L, vll C, vii U, vii V, vll T) {
    n = N;
    m = M;
    s = S;
    q = Q;
    for (int i = 0; i < m; i++) {
        int u = A[i] + 1, v = B[i] + 1;
        adj[u].push_back({v, i + 1});
        adj[v].push_back({u, i + 1});
        l[i + 1] = L[i];
        c[i + 1] = C[i] - L[i];
    }
    for (int i = 0; i < q; i++) {
        x[i + 1] = U[i] + 1;
        y[i + 1] = V[i] + 1;
        t[i + 1] = T[i];
    }
    solve();
    return writeOutput();
}

/*int main() {
    int n, m;
    ll s;
    int q;
    vii A, B, U, V;
    vll L, C, T;
    cin >> n >> m >> s >> q;
    for (int i = 1; i <= m; i++) {
        int x, y;
        ll z, t;
        cin >> x >> y >> z >> t;
        A.push_back(x);
        B.push_back(y);
        L.push_back(z);
        C.push_back(t);
    }
    int Q = q;
    U.resize(Q);
    V.resize(Q);
    T.resize(Q);
    for (int i = 0; i < q; i++)
        cin >> U[i] >> V[i] >> T[i];
    vll ans = calculate_necessary_time(n, m, s, q, A, B, L, C, U, V, T);
    for (auto x: ans)
        cout << x << endl;
    return 0;
}*/

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