oj.uz

Submission #921205

# Submission time Handle Problem Language Result Execution time Memory
921205 2024-02-03T13:44:30 Z bachhoangxuan Escape Route (JOI21_escape_route) C++17
100 / 100
 3048 ms 203860 KB 
#include "escape_route.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const ll inf=1e18;

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

    vector<vector<ll>> c(N,vector<ll>(N,S));
    vector<vector<ll>> l(N,vector<ll>(N,S));
    for(int i=0;i<M;i++){
        c[A[i]][B[i]]=c[B[i]][A[i]]=C[i];
        l[A[i]][B[i]]=l[B[i]][A[i]]=L[i];
    }
    for(int i=0;i<N;i++){
        c[i][i]=l[i][i]=0;
    }
    auto dijisktra = [&](int p,int s){
        vector<ll> d(N,inf);
        vector<bool> used(N,false);
        d[s]=c[p][s];
        for(int _=0;_<N;_++){
            int u=-1;
            for(int i=0;i<N;i++) if(!used[i] && (u==-1 || d[i]<d[u])) u=i;
            used[u]=true;
            for(int v=0;v<N;v++){
                if(used[v] || c[u][v]>=S) continue;
                ll dd=d[u]+l[u][v];
                if(d[u]%S+l[u][v]>c[u][v]) dd+=S-d[u]%S;
                d[v]=min(d[v],dd);
            }
        }
        return d;
    };

    vector<vector<vector<ll>>> d(N,vector<vector<ll>>(N,vector<ll>(N,inf)));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) if(c[i][j]<S) d[i][j]=dijisktra(i,j);

    vector<ll> res(Q,inf);
    for(int i=0;i<Q;i++){
        res[i]=d[U[i]][U[i]][V[i]]+(S-T[i])%S;
    }

    for(int st=0;st<N;st++){
        vector<pair<ll,int>> qq;
        for(int i=0;i<Q;i++) if(U[i]==st) qq.push_back({T[i],i});
        sort(qq.begin(),qq.end());
        vector<vector<pair<ll,int>>> ord(N);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++) if(i!=j && c[i][j]<S) ord[i].push_back({c[i][j]-l[i][j],j});
            sort(ord[i].rbegin(),ord[i].rend());
        }
        vector<int> pos(N,0);
        vector<ll> dd(N,inf);
        dd[st]=0;

        while(!qq.empty()){
            pair<ll,int> Max={-1,-1};
            for(int i=0;i<N;i++) if(pos[i]<(int)ord[i].size()) Max=max(Max,{ord[i][pos[i]].fi-dd[i],i});
            while(!qq.empty() && qq.back().fi>Max.fi){
                int id=qq.back().se;qq.pop_back();
                res[id]=min(res[id],dd[V[id]]);
                for(int i=0;i<N;i++){
                    if(dd[i]==inf) continue;
                    res[id]=min(res[id],S-T[id]+d[i][i][V[id]]);
                }
            }
            if(Max.fi==-1) break;
            int u=Max.se;
            int v=ord[u][pos[Max.se]++].se;
            for(int i=0;i<N;i++) if(d[u][v][i]<S) dd[i]=min(dd[i],d[u][v][i]-Max.fi);
        }
    }

    return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65112 KB Output is correct
2 Correct 16 ms 65116 KB Output is correct
3 Correct 38 ms 65116 KB Output is correct
4 Correct 10 ms 65112 KB Output is correct
5 Correct 23 ms 65112 KB Output is correct
6 Correct 12 ms 65116 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1349 ms 181392 KB Output is correct
2 Correct 1473 ms 189528 KB Output is correct
3 Correct 1376 ms 179536 KB Output is correct
4 Correct 1453 ms 199408 KB Output is correct
5 Correct 1404 ms 198932 KB Output is correct
6 Correct 11 ms 65116 KB Output is correct
7 Correct 1344 ms 181816 KB Output is correct
8 Correct 1369 ms 199404 KB Output is correct
9 Correct 1327 ms 181520 KB Output is correct
10 Correct 1363 ms 198736 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65112 KB Output is correct
2 Correct 16 ms 65116 KB Output is correct
3 Correct 38 ms 65116 KB Output is correct
4 Correct 10 ms 65112 KB Output is correct
5 Correct 23 ms 65112 KB Output is correct
6 Correct 12 ms 65116 KB Output is correct
7 Correct 1349 ms 181392 KB Output is correct
8 Correct 1473 ms 189528 KB Output is correct
9 Correct 1376 ms 179536 KB Output is correct
10 Correct 1453 ms 199408 KB Output is correct
11 Correct 1404 ms 198932 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 1344 ms 181816 KB Output is correct
14 Correct 1369 ms 199404 KB Output is correct
15 Correct 1327 ms 181520 KB Output is correct
16 Correct 1363 ms 198736 KB Output is correct
17 Correct 1774 ms 157128 KB Output is correct
18 Correct 1651 ms 157100 KB Output is correct
19 Correct 1756 ms 176076 KB Output is correct
20 Correct 1655 ms 156760 KB Output is correct
21 Correct 1715 ms 184976 KB Output is correct
22 Correct 1756 ms 185348 KB Output is correct
23 Correct 1720 ms 157140 KB Output is correct
24 Correct 1747 ms 197060 KB Output is correct
25 Correct 1647 ms 157272 KB Output is correct
26 Correct 1713 ms 185168 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65112 KB Output is correct
2 Correct 16 ms 65116 KB Output is correct
3 Correct 38 ms 65116 KB Output is correct
4 Correct 10 ms 65112 KB Output is correct
5 Correct 23 ms 65112 KB Output is correct
6 Correct 12 ms 65116 KB Output is correct
7 Correct 1349 ms 181392 KB Output is correct
8 Correct 1473 ms 189528 KB Output is correct
9 Correct 1376 ms 179536 KB Output is correct
10 Correct 1453 ms 199408 KB Output is correct
11 Correct 1404 ms 198932 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 1344 ms 181816 KB Output is correct
14 Correct 1369 ms 199404 KB Output is correct
15 Correct 1327 ms 181520 KB Output is correct
16 Correct 1363 ms 198736 KB Output is correct
17 Correct 1774 ms 157128 KB Output is correct
18 Correct 1651 ms 157100 KB Output is correct
19 Correct 1756 ms 176076 KB Output is correct
20 Correct 1655 ms 156760 KB Output is correct
21 Correct 1715 ms 184976 KB Output is correct
22 Correct 1756 ms 185348 KB Output is correct
23 Correct 1720 ms 157140 KB Output is correct
24 Correct 1747 ms 197060 KB Output is correct
25 Correct 1647 ms 157272 KB Output is correct
26 Correct 1713 ms 185168 KB Output is correct
27 Correct 2053 ms 157780 KB Output is correct
28 Correct 1989 ms 158048 KB Output is correct
29 Correct 2047 ms 176892 KB Output is correct
30 Correct 1998 ms 157604 KB Output is correct
31 Correct 2106 ms 186452 KB Output is correct
32 Correct 2152 ms 186128 KB Output is correct
33 Correct 1922 ms 199152 KB Output is correct
34 Correct 2045 ms 157828 KB Output is correct
35 Correct 2075 ms 186756 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 65112 KB Output is correct
2 Correct 16 ms 65116 KB Output is correct
3 Correct 38 ms 65116 KB Output is correct
4 Correct 10 ms 65112 KB Output is correct
5 Correct 23 ms 65112 KB Output is correct
6 Correct 12 ms 65116 KB Output is correct
7 Correct 1349 ms 181392 KB Output is correct
8 Correct 1473 ms 189528 KB Output is correct
9 Correct 1376 ms 179536 KB Output is correct
10 Correct 1453 ms 199408 KB Output is correct
11 Correct 1404 ms 198932 KB Output is correct
12 Correct 11 ms 65116 KB Output is correct
13 Correct 1344 ms 181816 KB Output is correct
14 Correct 1369 ms 199404 KB Output is correct
15 Correct 1327 ms 181520 KB Output is correct
16 Correct 1363 ms 198736 KB Output is correct
17 Correct 1774 ms 157128 KB Output is correct
18 Correct 1651 ms 157100 KB Output is correct
19 Correct 1756 ms 176076 KB Output is correct
20 Correct 1655 ms 156760 KB Output is correct
21 Correct 1715 ms 184976 KB Output is correct
22 Correct 1756 ms 185348 KB Output is correct
23 Correct 1720 ms 157140 KB Output is correct
24 Correct 1747 ms 197060 KB Output is correct
25 Correct 1647 ms 157272 KB Output is correct
26 Correct 1713 ms 185168 KB Output is correct
27 Correct 2053 ms 157780 KB Output is correct
28 Correct 1989 ms 158048 KB Output is correct
29 Correct 2047 ms 176892 KB Output is correct
30 Correct 1998 ms 157604 KB Output is correct
31 Correct 2106 ms 186452 KB Output is correct
32 Correct 2152 ms 186128 KB Output is correct
33 Correct 1922 ms 199152 KB Output is correct
34 Correct 2045 ms 157828 KB Output is correct
35 Correct 2075 ms 186756 KB Output is correct
36 Correct 3004 ms 159424 KB Output is correct
37 Correct 3016 ms 158192 KB Output is correct
38 Correct 2941 ms 162732 KB Output is correct
39 Correct 3048 ms 190844 KB Output is correct
40 Correct 3034 ms 191092 KB Output is correct
41 Correct 2284 ms 203860 KB Output is correct
42 Correct 3018 ms 158244 KB Output is correct
43 Correct 2961 ms 158168 KB Output is correct