oj.uz

Submission #617737

# Submission time Handle Problem Language Result Execution time Memory
617737 2022-08-01T13:05:32 Z qwerasdfzxcl Escape Route (JOI21_escape_route) C++17
70 / 100
 4233 ms 1744848 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);
}

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 64972 KB Output is correct
2 Correct 34 ms 64964 KB Output is correct
3 Correct 136 ms 67944 KB Output is correct
4 Correct 31 ms 64980 KB Output is correct
5 Correct 33 ms 65036 KB Output is correct
6 Correct 28 ms 64992 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 897 ms 279452 KB Output is correct
2 Correct 944 ms 285984 KB Output is correct
3 Correct 882 ms 277408 KB Output is correct
4 Correct 936 ms 285100 KB Output is correct
5 Correct 950 ms 297580 KB Output is correct
6 Correct 26 ms 64980 KB Output is correct
7 Correct 878 ms 281912 KB Output is correct
8 Correct 855 ms 237996 KB Output is correct
9 Correct 864 ms 273056 KB Output is correct
10 Correct 968 ms 296692 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 34 ms 64964 KB Output is correct
3 Correct 136 ms 67944 KB Output is correct
4 Correct 31 ms 64980 KB Output is correct
5 Correct 33 ms 65036 KB Output is correct
6 Correct 28 ms 64992 KB Output is correct
7 Correct 897 ms 279452 KB Output is correct
8 Correct 944 ms 285984 KB Output is correct
9 Correct 882 ms 277408 KB Output is correct
10 Correct 936 ms 285100 KB Output is correct
11 Correct 950 ms 297580 KB Output is correct
12 Correct 26 ms 64980 KB Output is correct
13 Correct 878 ms 281912 KB Output is correct
14 Correct 855 ms 237996 KB Output is correct
15 Correct 864 ms 273056 KB Output is correct
16 Correct 968 ms 296692 KB Output is correct
17 Correct 959 ms 274344 KB Output is correct
18 Correct 955 ms 270868 KB Output is correct
19 Correct 1082 ms 286372 KB Output is correct
20 Correct 990 ms 270360 KB Output is correct
21 Correct 1056 ms 285824 KB Output is correct
22 Correct 1036 ms 285584 KB Output is correct
23 Correct 942 ms 273088 KB Output is correct
24 Correct 868 ms 237008 KB Output is correct
25 Correct 973 ms 264684 KB Output is correct
26 Correct 1010 ms 285540 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 34 ms 64964 KB Output is correct
3 Correct 136 ms 67944 KB Output is correct
4 Correct 31 ms 64980 KB Output is correct
5 Correct 33 ms 65036 KB Output is correct
6 Correct 28 ms 64992 KB Output is correct
7 Correct 897 ms 279452 KB Output is correct
8 Correct 944 ms 285984 KB Output is correct
9 Correct 882 ms 277408 KB Output is correct
10 Correct 936 ms 285100 KB Output is correct
11 Correct 950 ms 297580 KB Output is correct
12 Correct 26 ms 64980 KB Output is correct
13 Correct 878 ms 281912 KB Output is correct
14 Correct 855 ms 237996 KB Output is correct
15 Correct 864 ms 273056 KB Output is correct
16 Correct 968 ms 296692 KB Output is correct
17 Correct 959 ms 274344 KB Output is correct
18 Correct 955 ms 270868 KB Output is correct
19 Correct 1082 ms 286372 KB Output is correct
20 Correct 990 ms 270360 KB Output is correct
21 Correct 1056 ms 285824 KB Output is correct
22 Correct 1036 ms 285584 KB Output is correct
23 Correct 942 ms 273088 KB Output is correct
24 Correct 868 ms 237008 KB Output is correct
25 Correct 973 ms 264684 KB Output is correct
26 Correct 1010 ms 285540 KB Output is correct
27 Correct 1517 ms 527464 KB Output is correct
28 Correct 1466 ms 515972 KB Output is correct
29 Correct 1577 ms 538412 KB Output is correct
30 Correct 1441 ms 495680 KB Output is correct
31 Correct 1544 ms 529456 KB Output is correct
32 Correct 1691 ms 529584 KB Output is correct
33 Correct 1109 ms 245872 KB Output is correct
34 Correct 1486 ms 515820 KB Output is correct
35 Correct 1548 ms 546432 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 64972 KB Output is correct
2 Correct 34 ms 64964 KB Output is correct
3 Correct 136 ms 67944 KB Output is correct
4 Correct 31 ms 64980 KB Output is correct
5 Correct 33 ms 65036 KB Output is correct
6 Correct 28 ms 64992 KB Output is correct
7 Correct 897 ms 279452 KB Output is correct
8 Correct 944 ms 285984 KB Output is correct
9 Correct 882 ms 277408 KB Output is correct
10 Correct 936 ms 285100 KB Output is correct
11 Correct 950 ms 297580 KB Output is correct
12 Correct 26 ms 64980 KB Output is correct
13 Correct 878 ms 281912 KB Output is correct
14 Correct 855 ms 237996 KB Output is correct
15 Correct 864 ms 273056 KB Output is correct
16 Correct 968 ms 296692 KB Output is correct
17 Correct 959 ms 274344 KB Output is correct
18 Correct 955 ms 270868 KB Output is correct
19 Correct 1082 ms 286372 KB Output is correct
20 Correct 990 ms 270360 KB Output is correct
21 Correct 1056 ms 285824 KB Output is correct
22 Correct 1036 ms 285584 KB Output is correct
23 Correct 942 ms 273088 KB Output is correct
24 Correct 868 ms 237008 KB Output is correct
25 Correct 973 ms 264684 KB Output is correct
26 Correct 1010 ms 285540 KB Output is correct
27 Correct 1517 ms 527464 KB Output is correct
28 Correct 1466 ms 515972 KB Output is correct
29 Correct 1577 ms 538412 KB Output is correct
30 Correct 1441 ms 495680 KB Output is correct
31 Correct 1544 ms 529456 KB Output is correct
32 Correct 1691 ms 529584 KB Output is correct
33 Correct 1109 ms 245872 KB Output is correct
34 Correct 1486 ms 515820 KB Output is correct
35 Correct 1548 ms 546432 KB Output is correct
36 Incorrect 4233 ms 1744848 KB Output isn't correct
37 Halted 0 ms 0 KB -