제출 #617592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617592		qwerasdfzxcl	Escape Route (JOI21_escape_route)	C++17	70 / 100	9190 ms	1709148 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[101][101];
int n, m, q, idx[101][9090];
ll MOD, dist0[101][101], dist[101][101][9090], sz[101];
pair<ll, int> ran[101][9090];
vector<pair<ll, int>> DB[101][101];
bool visited[101];

vector<ll> ans;

void dijkstra(int s, ll t, ll dist[], bool is0){
    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[]){
    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 = -INF, 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;

    //printf("\n %d %d (Enum = %d)\n", x, y, Enum);
    for (int i=1;i<=n;i++) if (distx[i] > -INF){
        ran[i][sz[i]] = {distx[i]+1, Enum};
        ++sz[i];
        for (int j=1;j<=n;j++) if (distx[i] > -INF && disty[j] < INF){
            //printf(" %d -> %d: %lld -> %lld\n", i, j, distx[i], disty[j]);
            DB[i][j].emplace_back(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++){
        //printf("\n%d %d\n", s, v);
        fill(dist[s][v], dist[s][v]+sz[s]+1, INF);

        for (auto &[d, e]:DB[s][v]){
            //printf(" %lld %d(->%d)\n", d, e, idx[s][e]);
            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]);
            //printf("%lld ", dist[s][v][i]);
        }
        //printf("\n");
    }

    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