oj.uz

Submission #709771

# Submission time Handle Problem Language Result Execution time Memory
709771 2023-03-14T11:50:16 Z Jarif_Rahman Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 281000 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll inf = 5e17;

vector<ll> calculate_necessary_time(int n, int m, ll S, int q, vector<int> A, vector<int> B,
    vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T){

    vector<ll> ans(q, inf);
    vector<vector<tuple<int, ll, ll>>> v(n);
    
    for(int i = 0; i < m; i++){
        v[A[i]].pb({B[i], L[i], C[i]});
        v[B[i]].pb({A[i], L[i], C[i]});
    }

    vector<vector<ll>> dis2(n);

    for(int s = 0; s < n; s++){
        dis2[s].assign(n, inf);
        vector<bool> bl(n, 0);
        priority_queue<pair<ll, int>> pq;

        dis2[s][s] = 0;
        pq.push({0, s});

        while(!pq.empty()){
            int nd = pq.top().sc; pq.pop();
            if(bl[nd]) continue;
            bl[nd] = 1;

            for(auto [x, l, c]: v[nd])
                if((dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l) < dis2[s][x]){
                dis2[s][x] = (dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l);
                pq.push({-dis2[s][x], x});
            }
        }
    }

    vector<vector<vector<ll>>> dis1(n);
    vector<vector<ll>> sth(n);

    for(int s = 0; s < n; s++){
        ll t = 0;
        while(1){
            ll nxt = inf;
            sth[s].pb(t);
            dis1[s].pb(vector<ll>(n));
            auto &dis = dis1[s].back();

            dis.assign(n, inf);
            vector<ll> change(n, inf);
            vector<bool> bl(n, 0);
            priority_queue<pair<ll, int>> pq;

            dis[s] = t;
            pq.push({0, s});

            while(!pq.empty()){
                int nd = pq.top().sc; pq.pop();
                if(bl[nd]) continue;
                bl[nd] = 1;

                for(auto [x, l, c]: v[nd]) if(dis[nd]+l <= min(dis[x]-1, c)){
                    dis[x] = dis[nd]+l;
                    change[x] = c-dis[x]+1;
                    pq.push({-dis[x], x});
                }
            }

            for(ll &x: dis) if(x != inf) x-=t;
            nxt = min(nxt, *min_element(change.begin(), change.end()));

            if(nxt == inf) break;
            t+=nxt;
        }
    }

    for(int i = 0; i < q; i++){
        int p = (upper_bound(sth[U[i]].begin(), sth[U[i]].end(), T[i])-sth[U[i]].begin())-1;
        if(dis1[U[i]][p][V[i]] != inf){
            ans[i] = min(ans[i], dis1[U[i]][p][V[i]]);
            continue;
        }
        for(int j = 0; j < n; j++) if(dis1[U[i]][p][j] != inf)
            ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]);
    }

    return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 28 ms 65008 KB Output is correct
3 Correct 61 ms 65108 KB Output is correct
4 Correct 26 ms 65036 KB Output is correct
5 Correct 26 ms 64996 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 718 ms 116912 KB Output is correct
2 Correct 789 ms 139704 KB Output is correct
3 Correct 456 ms 122908 KB Output is correct
4 Correct 877 ms 142060 KB Output is correct
5 Correct 892 ms 143180 KB Output is correct
6 Correct 24 ms 64992 KB Output is correct
7 Correct 438 ms 122144 KB Output is correct
8 Correct 511 ms 144372 KB Output is correct
9 Correct 601 ms 121896 KB Output is correct
10 Correct 930 ms 140768 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 28 ms 65008 KB Output is correct
3 Correct 61 ms 65108 KB Output is correct
4 Correct 26 ms 65036 KB Output is correct
5 Correct 26 ms 64996 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 718 ms 116912 KB Output is correct
8 Correct 789 ms 139704 KB Output is correct
9 Correct 456 ms 122908 KB Output is correct
10 Correct 877 ms 142060 KB Output is correct
11 Correct 892 ms 143180 KB Output is correct
12 Correct 24 ms 64992 KB Output is correct
13 Correct 438 ms 122144 KB Output is correct
14 Correct 511 ms 144372 KB Output is correct
15 Correct 601 ms 121896 KB Output is correct
16 Correct 930 ms 140768 KB Output is correct
17 Correct 700 ms 160152 KB Output is correct
18 Correct 782 ms 160156 KB Output is correct
19 Correct 821 ms 185632 KB Output is correct
20 Correct 570 ms 156752 KB Output is correct
21 Correct 1014 ms 176768 KB Output is correct
22 Correct 1116 ms 177196 KB Output is correct
23 Correct 503 ms 157176 KB Output is correct
24 Correct 615 ms 176384 KB Output is correct
25 Correct 823 ms 157048 KB Output is correct
26 Correct 1112 ms 173696 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 28 ms 65008 KB Output is correct
3 Correct 61 ms 65108 KB Output is correct
4 Correct 26 ms 65036 KB Output is correct
5 Correct 26 ms 64996 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 718 ms 116912 KB Output is correct
8 Correct 789 ms 139704 KB Output is correct
9 Correct 456 ms 122908 KB Output is correct
10 Correct 877 ms 142060 KB Output is correct
11 Correct 892 ms 143180 KB Output is correct
12 Correct 24 ms 64992 KB Output is correct
13 Correct 438 ms 122144 KB Output is correct
14 Correct 511 ms 144372 KB Output is correct
15 Correct 601 ms 121896 KB Output is correct
16 Correct 930 ms 140768 KB Output is correct
17 Correct 700 ms 160152 KB Output is correct
18 Correct 782 ms 160156 KB Output is correct
19 Correct 821 ms 185632 KB Output is correct
20 Correct 570 ms 156752 KB Output is correct
21 Correct 1014 ms 176768 KB Output is correct
22 Correct 1116 ms 177196 KB Output is correct
23 Correct 503 ms 157176 KB Output is correct
24 Correct 615 ms 176384 KB Output is correct
25 Correct 823 ms 157048 KB Output is correct
26 Correct 1112 ms 173696 KB Output is correct
27 Correct 2143 ms 188944 KB Output is correct
28 Correct 2755 ms 191556 KB Output is correct
29 Correct 3564 ms 217340 KB Output is correct
30 Correct 804 ms 159632 KB Output is correct
31 Correct 3799 ms 225720 KB Output is correct
32 Correct 3402 ms 224756 KB Output is correct
33 Correct 665 ms 191876 KB Output is correct
34 Correct 1827 ms 171492 KB Output is correct
35 Correct 3125 ms 223052 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 64972 KB Output is correct
2 Correct 28 ms 65008 KB Output is correct
3 Correct 61 ms 65108 KB Output is correct
4 Correct 26 ms 65036 KB Output is correct
5 Correct 26 ms 64996 KB Output is correct
6 Correct 25 ms 64968 KB Output is correct
7 Correct 718 ms 116912 KB Output is correct
8 Correct 789 ms 139704 KB Output is correct
9 Correct 456 ms 122908 KB Output is correct
10 Correct 877 ms 142060 KB Output is correct
11 Correct 892 ms 143180 KB Output is correct
12 Correct 24 ms 64992 KB Output is correct
13 Correct 438 ms 122144 KB Output is correct
14 Correct 511 ms 144372 KB Output is correct
15 Correct 601 ms 121896 KB Output is correct
16 Correct 930 ms 140768 KB Output is correct
17 Correct 700 ms 160152 KB Output is correct
18 Correct 782 ms 160156 KB Output is correct
19 Correct 821 ms 185632 KB Output is correct
20 Correct 570 ms 156752 KB Output is correct
21 Correct 1014 ms 176768 KB Output is correct
22 Correct 1116 ms 177196 KB Output is correct
23 Correct 503 ms 157176 KB Output is correct
24 Correct 615 ms 176384 KB Output is correct
25 Correct 823 ms 157048 KB Output is correct
26 Correct 1112 ms 173696 KB Output is correct
27 Correct 2143 ms 188944 KB Output is correct
28 Correct 2755 ms 191556 KB Output is correct
29 Correct 3564 ms 217340 KB Output is correct
30 Correct 804 ms 159632 KB Output is correct
31 Correct 3799 ms 225720 KB Output is correct
32 Correct 3402 ms 224756 KB Output is correct
33 Correct 665 ms 191876 KB Output is correct
34 Correct 1827 ms 171492 KB Output is correct
35 Correct 3125 ms 223052 KB Output is correct
36 Correct 8210 ms 281000 KB Output is correct
37 Execution timed out 9096 ms 272140 KB Time limit exceeded
38 Halted 0 ms 0 KB -