oj.uz

Submission #617741

# Submission time Handle Problem Language Result Execution time Memory
617741 2022-08-01T13:08:09 Z qwerasdfzxcl Escape Route (JOI21_escape_route) C++17
100 / 100
 4306 ms 1770192 KB 
#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+1));
    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+1));
    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] > -1){
        ran[i][sz[i]++] = {distx[i]+1, Enum};

        for (int j=1;j<=n;j++) if (distx[i] > -1 && 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);
}

struct FUCK{
    int u, v, i;
    ll t;
    FUCK(){}
    FUCK(int _u, int _v, ll _t, int _i): u(_u), v(_v), i(_i), t(_t) {}
    bool operator<(const FUCK &FUUUUUCK) const{
        return tie(u, t) < tie(FUUUUUCK.u, FUUUUUCK.t);
    }
}fuck[3003000];

int fuuck[101];

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);

    //if (n>60) exit(0);
    for (int i=0;i<q;i++) fuck[i] = FUCK(U[i]+1, V[i]+1, T[i], i);
    sort(fuck, fuck+q);
    ans.resize(q);

    for (int i=0;i<q;i++){
        int u = fuck[i].u;
        int v = fuck[i].v;
        int ii = fuck[i].i;
        ll t = fuck[i].t;

        while(fuuck[u]<sz[u] && ran[u][fuuck[u]].first <=  t) fuuck[u]++;
        int pt = fuuck[u] - 1;
        //printf(" %d %d %lld -> %d\n", U[i], V[i], T[i], pt);
        ll ret = dist[u][v][pt];
        for (int j=1;j<=n;j++) if (dist[u][j][pt]<INF){
            ret = min(ret, MOD - t + dist0[j][v]);
        }
        ans[ii] = ret;
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 35 ms 65008 KB Output is correct
3 Correct 145 ms 68008 KB Output is correct
4 Correct 26 ms 64980 KB Output is correct
5 Correct 34 ms 64980 KB Output is correct
6 Correct 28 ms 65036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 274912 KB Output is correct
2 Correct 951 ms 285952 KB Output is correct
3 Correct 871 ms 272120 KB Output is correct
4 Correct 989 ms 289892 KB Output is correct
5 Correct 951 ms 292724 KB Output is correct
6 Correct 28 ms 65108 KB Output is correct
7 Correct 902 ms 276148 KB Output is correct
8 Correct 865 ms 238124 KB Output is correct
9 Correct 911 ms 267568 KB Output is correct
10 Correct 1014 ms 292536 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 35 ms 65008 KB Output is correct
3 Correct 145 ms 68008 KB Output is correct
4 Correct 26 ms 64980 KB Output is correct
5 Correct 34 ms 64980 KB Output is correct
6 Correct 28 ms 65036 KB Output is correct
7 Correct 876 ms 274912 KB Output is correct
8 Correct 951 ms 285952 KB Output is correct
9 Correct 871 ms 272120 KB Output is correct
10 Correct 989 ms 289892 KB Output is correct
11 Correct 951 ms 292724 KB Output is correct
12 Correct 28 ms 65108 KB Output is correct
13 Correct 902 ms 276148 KB Output is correct
14 Correct 865 ms 238124 KB Output is correct
15 Correct 911 ms 267568 KB Output is correct
16 Correct 1014 ms 292536 KB Output is correct
17 Correct 1031 ms 274372 KB Output is correct
18 Correct 997 ms 270776 KB Output is correct
19 Correct 1018 ms 286660 KB Output is correct
20 Correct 999 ms 270264 KB Output is correct
21 Correct 1022 ms 290608 KB Output is correct
22 Correct 1043 ms 290292 KB Output is correct
23 Correct 935 ms 273080 KB Output is correct
24 Correct 903 ms 241792 KB Output is correct
25 Correct 905 ms 264788 KB Output is correct
26 Correct 1016 ms 290332 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 35 ms 65008 KB Output is correct
3 Correct 145 ms 68008 KB Output is correct
4 Correct 26 ms 64980 KB Output is correct
5 Correct 34 ms 64980 KB Output is correct
6 Correct 28 ms 65036 KB Output is correct
7 Correct 876 ms 274912 KB Output is correct
8 Correct 951 ms 285952 KB Output is correct
9 Correct 871 ms 272120 KB Output is correct
10 Correct 989 ms 289892 KB Output is correct
11 Correct 951 ms 292724 KB Output is correct
12 Correct 28 ms 65108 KB Output is correct
13 Correct 902 ms 276148 KB Output is correct
14 Correct 865 ms 238124 KB Output is correct
15 Correct 911 ms 267568 KB Output is correct
16 Correct 1014 ms 292536 KB Output is correct
17 Correct 1031 ms 274372 KB Output is correct
18 Correct 997 ms 270776 KB Output is correct
19 Correct 1018 ms 286660 KB Output is correct
20 Correct 999 ms 270264 KB Output is correct
21 Correct 1022 ms 290608 KB Output is correct
22 Correct 1043 ms 290292 KB Output is correct
23 Correct 935 ms 273080 KB Output is correct
24 Correct 903 ms 241792 KB Output is correct
25 Correct 905 ms 264788 KB Output is correct
26 Correct 1016 ms 290332 KB Output is correct
27 Correct 1526 ms 527468 KB Output is correct
28 Correct 1497 ms 515900 KB Output is correct
29 Correct 1598 ms 531300 KB Output is correct
30 Correct 1489 ms 495652 KB Output is correct
31 Correct 1532 ms 534316 KB Output is correct
32 Correct 1559 ms 530004 KB Output is correct
33 Correct 985 ms 246124 KB Output is correct
34 Correct 1511 ms 515904 KB Output is correct
35 Correct 1535 ms 535444 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64980 KB Output is correct
2 Correct 35 ms 65008 KB Output is correct
3 Correct 145 ms 68008 KB Output is correct
4 Correct 26 ms 64980 KB Output is correct
5 Correct 34 ms 64980 KB Output is correct
6 Correct 28 ms 65036 KB Output is correct
7 Correct 876 ms 274912 KB Output is correct
8 Correct 951 ms 285952 KB Output is correct
9 Correct 871 ms 272120 KB Output is correct
10 Correct 989 ms 289892 KB Output is correct
11 Correct 951 ms 292724 KB Output is correct
12 Correct 28 ms 65108 KB Output is correct
13 Correct 902 ms 276148 KB Output is correct
14 Correct 865 ms 238124 KB Output is correct
15 Correct 911 ms 267568 KB Output is correct
16 Correct 1014 ms 292536 KB Output is correct
17 Correct 1031 ms 274372 KB Output is correct
18 Correct 997 ms 270776 KB Output is correct
19 Correct 1018 ms 286660 KB Output is correct
20 Correct 999 ms 270264 KB Output is correct
21 Correct 1022 ms 290608 KB Output is correct
22 Correct 1043 ms 290292 KB Output is correct
23 Correct 935 ms 273080 KB Output is correct
24 Correct 903 ms 241792 KB Output is correct
25 Correct 905 ms 264788 KB Output is correct
26 Correct 1016 ms 290332 KB Output is correct
27 Correct 1526 ms 527468 KB Output is correct
28 Correct 1497 ms 515900 KB Output is correct
29 Correct 1598 ms 531300 KB Output is correct
30 Correct 1489 ms 495652 KB Output is correct
31 Correct 1532 ms 534316 KB Output is correct
32 Correct 1559 ms 530004 KB Output is correct
33 Correct 985 ms 246124 KB Output is correct
34 Correct 1511 ms 515904 KB Output is correct
35 Correct 1535 ms 535444 KB Output is correct
36 Correct 4146 ms 1749664 KB Output is correct
37 Correct 4306 ms 1762908 KB Output is correct
38 Correct 3921 ms 1659408 KB Output is correct
39 Correct 4234 ms 1742888 KB Output is correct
40 Correct 4117 ms 1747400 KB Output is correct
41 Correct 1109 ms 327336 KB Output is correct
42 Correct 4070 ms 1770192 KB Output is correct
43 Correct 4221 ms 1752740 KB Output is correct