Submission #1171578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171578		OI_Account	Escape Route (JOI21_escape_route)	C++20	70 / 100	9065 ms	291260 KiB

escape_route

#pragma GCC optimize("O2,unroll-loops,Ofast")
#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 = 8100;
const int Q = 3'000'000;
const ll INF = 1'000'000'000'000'000'000;

int n, m, q, ed[N + 10][N + 10];
int par[N + 10], parE[N + 10];
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];
vector<int> vec, remain;
bool mark[N + 10];
int pntSt, lst[N + 10], nxt[N + 10];

void calcDisType1(int r, ll timSt) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    priority_queue<pair<ll, int>> st;
    st.push({0, r});
    d[r] = 0;
    tim[r] = timSt;
    while (!st.empty()) {
        int u = st.top().second;
        ll last = -st.top().first;
        st.pop();
        if (last != d[u])
            continue;
        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]) {
                d[v] = newDis;
                tim[v] = newTim;
                st.push({-d[v], v});
            }
        }
    }
}

void init() {
    pntSt = 1;
    for (int i = 1; i <= n; i++) {
        lst[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n] = 0;
}

void del(int u) {
    if (pntSt == u)
        pntSt = nxt[u];
    int x = lst[u], y = nxt[u];
    if (x)
        nxt[x] = y;
    if (y)
        lst[y] = x;
}

void calcDisType2(int r, ll timSt, bool use = true) {
    init();
    fill(mark + 1, mark + n + 1, false);
    priority_queue<pair<ll, int>> st; 
    st.push({0, r});
    d[r] = 0;
    tim[r] = timSt;
    mark[r] = true;
    del(r);
    if (use) {
        for (int i = 1; i < (int) vec.size(); i++) {
            int u = vec[i];
            if (mark[par[u]] && tim[par[u]] <= c[parE[u]]) {
                mark[u] = true;
                tim[u] = tim[par[u]] + l[parE[u]];
                st.push({-d[u], u});
            }
        }
        for (int u = 1; u <= n; u++)
            if (!mark[u] && d[u] == INF) {
                mark[u] = true;
                par[u] = parE[u] = 0;
                del(u);
            }
    }
    vec.clear();
    for (int i = 1; i <= n; i++) 
        if (!mark[i]){
            d[i] = INF;
            par[i] = 0;
        }
    while (!st.empty()) {
        int u = st.top().second;
        ll last = -st.top().first;
        st.pop();
        if (last != d[u])
            continue;
        vec.push_back(u);
        if (!mark[u])
            del(u);
        int pnt = pntSt;
        while (pnt) {
            int v = pnt;
            int e = ed[u][v];
            if (e) {
                if (tim[u] <= c[e] && d[u] + l[e] < d[v]) {
                    d[v] = d[u] + l[e];
                    tim[v] = tim[u] + l[e];
                    par[v] = u;
                    parE[v] = e;
                    st.push({-d[v], v});
                }
            }
            pnt = nxt[pnt];
        }
    }
}

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, false);
    for (int i = 1; i <= n; i++)
        dis[u][0][i] = d[i];
    int pnt = 0;
    while (true) {
        ll mn = INF;
        for (int i = 1; i <= n; i++)
            if (par[i])
                mn = min(mn, c[parE[i]] - (imp[u].back() + d[par[i]]));
        if (mn == INF)
            break;
        ll tmp = imp[u].back() + mn + 1;
        calcDisType2(u, tmp);
        pnt++;
        for (int v = 1; v <= n; v++)
            dis[u][pnt][v] = d[v];
        imp[u].push_back(tmp);
    }
}

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];
        ed[u][v] = ed[v][u] = i + 1;
    }
    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: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 35 / 35
• Subtask 5: 0 / 30