oj.uz

Submission #617649

# Submission time Handle Problem Language Result Execution time Memory
617649 2022-08-01T12:36:53 Z qwerasdfzxcl Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 1699640 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+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] > -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);
}

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64988 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 148 ms 67792 KB Output is correct
4 Correct 29 ms 65056 KB Output is correct
5 Correct 41 ms 65060 KB Output is correct
6 Correct 37 ms 65068 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 239516 KB Output is correct
2 Correct 820 ms 225424 KB Output is correct
3 Correct 926 ms 238236 KB Output is correct
4 Correct 898 ms 243148 KB Output is correct
5 Correct 1028 ms 240532 KB Output is correct
6 Correct 29 ms 64916 KB Output is correct
7 Correct 876 ms 242644 KB Output is correct
8 Correct 522 ms 177672 KB Output is correct
9 Correct 766 ms 233956 KB Output is correct
10 Correct 878 ms 239360 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64988 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 148 ms 67792 KB Output is correct
4 Correct 29 ms 65056 KB Output is correct
5 Correct 41 ms 65060 KB Output is correct
6 Correct 37 ms 65068 KB Output is correct
7 Correct 987 ms 239516 KB Output is correct
8 Correct 820 ms 225424 KB Output is correct
9 Correct 926 ms 238236 KB Output is correct
10 Correct 898 ms 243148 KB Output is correct
11 Correct 1028 ms 240532 KB Output is correct
12 Correct 29 ms 64916 KB Output is correct
13 Correct 876 ms 242644 KB Output is correct
14 Correct 522 ms 177672 KB Output is correct
15 Correct 766 ms 233956 KB Output is correct
16 Correct 878 ms 239360 KB Output is correct
17 Correct 2625 ms 218428 KB Output is correct
18 Correct 2477 ms 225824 KB Output is correct
19 Correct 1931 ms 225892 KB Output is correct
20 Correct 2560 ms 222664 KB Output is correct
21 Correct 2452 ms 243928 KB Output is correct
22 Correct 2574 ms 244044 KB Output is correct
23 Correct 2355 ms 218016 KB Output is correct
24 Correct 1220 ms 195700 KB Output is correct
25 Correct 2549 ms 205024 KB Output is correct
26 Correct 2581 ms 243588 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64988 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 148 ms 67792 KB Output is correct
4 Correct 29 ms 65056 KB Output is correct
5 Correct 41 ms 65060 KB Output is correct
6 Correct 37 ms 65068 KB Output is correct
7 Correct 987 ms 239516 KB Output is correct
8 Correct 820 ms 225424 KB Output is correct
9 Correct 926 ms 238236 KB Output is correct
10 Correct 898 ms 243148 KB Output is correct
11 Correct 1028 ms 240532 KB Output is correct
12 Correct 29 ms 64916 KB Output is correct
13 Correct 876 ms 242644 KB Output is correct
14 Correct 522 ms 177672 KB Output is correct
15 Correct 766 ms 233956 KB Output is correct
16 Correct 878 ms 239360 KB Output is correct
17 Correct 2625 ms 218428 KB Output is correct
18 Correct 2477 ms 225824 KB Output is correct
19 Correct 1931 ms 225892 KB Output is correct
20 Correct 2560 ms 222664 KB Output is correct
21 Correct 2452 ms 243928 KB Output is correct
22 Correct 2574 ms 244044 KB Output is correct
23 Correct 2355 ms 218016 KB Output is correct
24 Correct 1220 ms 195700 KB Output is correct
25 Correct 2549 ms 205024 KB Output is correct
26 Correct 2581 ms 243588 KB Output is correct
27 Correct 4661 ms 466636 KB Output is correct
28 Correct 4671 ms 464712 KB Output is correct
29 Correct 3111 ms 482908 KB Output is correct
30 Correct 3972 ms 450092 KB Output is correct
31 Correct 4211 ms 488768 KB Output is correct
32 Correct 4070 ms 486324 KB Output is correct
33 Correct 2300 ms 202144 KB Output is correct
34 Correct 4080 ms 470572 KB Output is correct
35 Correct 4159 ms 500676 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 64988 KB Output is correct
2 Correct 37 ms 65024 KB Output is correct
3 Correct 148 ms 67792 KB Output is correct
4 Correct 29 ms 65056 KB Output is correct
5 Correct 41 ms 65060 KB Output is correct
6 Correct 37 ms 65068 KB Output is correct
7 Correct 987 ms 239516 KB Output is correct
8 Correct 820 ms 225424 KB Output is correct
9 Correct 926 ms 238236 KB Output is correct
10 Correct 898 ms 243148 KB Output is correct
11 Correct 1028 ms 240532 KB Output is correct
12 Correct 29 ms 64916 KB Output is correct
13 Correct 876 ms 242644 KB Output is correct
14 Correct 522 ms 177672 KB Output is correct
15 Correct 766 ms 233956 KB Output is correct
16 Correct 878 ms 239360 KB Output is correct
17 Correct 2625 ms 218428 KB Output is correct
18 Correct 2477 ms 225824 KB Output is correct
19 Correct 1931 ms 225892 KB Output is correct
20 Correct 2560 ms 222664 KB Output is correct
21 Correct 2452 ms 243928 KB Output is correct
22 Correct 2574 ms 244044 KB Output is correct
23 Correct 2355 ms 218016 KB Output is correct
24 Correct 1220 ms 195700 KB Output is correct
25 Correct 2549 ms 205024 KB Output is correct
26 Correct 2581 ms 243588 KB Output is correct
27 Correct 4661 ms 466636 KB Output is correct
28 Correct 4671 ms 464712 KB Output is correct
29 Correct 3111 ms 482908 KB Output is correct
30 Correct 3972 ms 450092 KB Output is correct
31 Correct 4211 ms 488768 KB Output is correct
32 Correct 4070 ms 486324 KB Output is correct
33 Correct 2300 ms 202144 KB Output is correct
34 Correct 4080 ms 470572 KB Output is correct
35 Correct 4159 ms 500676 KB Output is correct
36 Execution timed out 9103 ms 1699640 KB Time limit exceeded
37 Halted 0 ms 0 KB -