Submission #617642

#	Time	Username	Problem	Language	Result	Execution time	Memory
617642		qwerasdfzxcl	Escape Route (JOI21_escape_route)	C++17	70 / 100	9238 ms	1684884 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 4e18;
pair<ll, ll> adj[91][91];
int n, m, q, idx[91][8102];
ll MOD, dist0[91][91], dist[91][91][8102], sz[91], sz2[91][91];
pair<ll, int> ran[91][8102], DB[91][91][8102];
bool visited[91];

vector<ll> ans;

void dijkstra(int s, ll t, ll dist[], bool is0){
    memset(dist, 0x3f, sizeof(ll)*(n+2));
    memset(visited, 0, sizeof(visited));
    //fill(dist+1, dist+n+1, INF);
    //fill(visited+1, visited+n+1, 0);

    dist[s] = t;

    for (int i=1;i<=n;i++){
        ll mn = INF, v = -1;
        for (int j=1;j<=n;j++) if (!visited[j] && mn > dist[j]) mn = dist[j], v = j;
        if (v==-1) break;

        visited[v] = 1;
        //printf(" %d %lld\n", v, mn);

        for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){
            auto &[l, c] = adj[v][nxt];

            ll nt = mn + l;

            if (!is0){
                if (mn>c-l) continue;
            }
            else if (mn%MOD > c-l){
                nt = (mn/MOD*MOD + MOD) + l;
            }

            if (nt < dist[nxt]){
                dist[nxt] = nt;
            }
        }
    }

}

void dijkINV(int s, ll t, ll dist[]){
    memset(dist, -1, sizeof(ll)*(n+2));
    memset(visited, 0, sizeof(visited));
    //fill(dist+1, dist+n+1, -INF);
    //fill(visited+1, visited+n+1, 0);

    dist[s] = t;

    for (int i=1;i<=n;i++){
        ll mx = -1, v = -1;
        for (int j=1;j<=n;j++) if (!visited[j] && mx < dist[j]) mx = dist[j], v = j;
        if (v==-1) break;

        visited[v] = 1;

        for (int nxt=1;nxt<=n;nxt++) if (!visited[nxt] && adj[v][nxt].first){
            auto &[l, c] = adj[v][nxt];

            ll nt = mx - l;

            if (nt > c-l) continue;

            if (nt > dist[nxt]){
                dist[nxt] = nt;
            }
        }
    }
}

ll distx[101], disty[101];
int Enum;
void calc(int x, int y){
    if (!adj[x][y].first) return;
    auto [l, c] = adj[x][y];

    dijkINV(x, c-l, distx);
    dijkstra(y, c, disty, 0);
    ++Enum;

    for (int i=1;i<=n;i++) if (distx[i] > -INF){
        ran[i][sz[i]++] = {distx[i]+1, Enum};

        for (int j=1;j<=n;j++) if (distx[i] > -INF && disty[j] < INF){
            DB[i][j][sz2[i][j]++] = {disty[j] - distx[i], Enum};
        }
    }
}

void init(int s){
    sort(ran[s], ran[s]+sz[s]);
    for (int i=1;i<sz[s];i++) idx[s][ran[s][i].second] = i;

    for (int v=1;v<=n;v++){
        memset(dist[s][v], 0x3f, sizeof(ll)*(sz[s]+1));
        //fill(dist[s][v], dist[s][v]+sz[s]+1, INF);

        for (int i=0;i<sz2[s][v];i++){
            auto &[d, e] = DB[s][v][i];
            dist[s][v][idx[s][e]-1] = d;
        }
        for (int i=sz[s]-1;i>=0;i--){
            dist[s][v][i] = min(dist[s][v][i], dist[s][v][i+1]);
        }
    }

    memset(dist[s][s], 0, sizeof(ll)*(sz[s]+1));
    //fill(dist[s][s], dist[s][s]+sz[s], 0);
}

std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q, std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
    std::vector<int> V, std::vector<long long> T) {

    n = N, m = M, MOD = S, q = Q;
    for (int i=0;i<m;i++){
        ++A[i], ++B[i];

        adj[A[i]][B[i]] = make_pair(L[i], C[i]);
        adj[B[i]][A[i]] = make_pair(L[i], C[i]);
    }

    for (int i=1;i<=n;i++) dijkstra(i, 0, dist0[i], 1);

    fill(sz+1, sz+n+1, 1);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++) calc(i, j);
    }

    for (int i=1;i<=n;i++) init(i);

    for (int i=0;i<q;i++){
        ++U[i], ++V[i];

        int pt = upper_bound(ran[U[i]], ran[U[i]]+sz[U[i]], make_pair(T[i], (int)1e9)) - ran[U[i]] - 1;
        //printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt);
        ll ret = dist[U[i]][V[i]][pt];
        for (int j=1;j<=n;j++) if (dist[U[i]][j][pt]<INF){
            ret = min(ret, MOD - T[i] + dist0[j][V[i]]);
        }
        ans.push_back(ret);
    }

    return ans;
}

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