oj.uz

Submission #532926

# Submission time Handle Problem Language Result Execution time Memory
532926 2022-03-04T08:43:42 Z nafis_shifat Escape Route (JOI21_escape_route) C++17
70 / 100
 9000 ms 289748 KB 
#include "escape_route.h"
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
const ll inf = 1e18;
const int mxn = 3e6 + 5;
using namespace std;


vector<int> adj[mxn];
int n, m;
ll s, q;
int l[mxn], r[mxn];
ll c[mxn], w[mxn];


ll q_t[mxn];

int block[mxn] = {};

void dijkstra1(int source, pii *dist) {
    int vis[n + 1] = {};

    for(int i = 0; i < n; i++) dist[i] = {inf, inf};
    dist[source] = {0, 0};


    for(int i = 0; i < n; i++) {
        int u = -1;
        pii cur = {inf, inf};

        for(int j = 0; j < n; j++) {
            if(vis[j]) continue;
            if(dist[j] < cur) {
                cur = dist[j];
                u = j;
            }

        }

        if(u == -1) break;

        vis[u] = 1;

        ll T = dist[u].second;
        ll d = dist[u].first;



        for(int i : adj[u]) {
            int v = l[i] ^ r[i] ^ u;


            if(T + w[i] <= c[i]) {
                if(dist[v] > make_pair(d, T + w[i])) {
                    dist[v] = make_pair(d, T + w[i]);
                } 
            }
            dist[v] = min(dist[v], {d + 1, w[i]});
        }


    }


}


pii dijkstra2(int source, ll *dist) {
    int vis[n + 1] = {};

    for(int i = 0; i < n; i++) dist[i] = inf;
    dist[source] = 0;

    ll mn = inf;

    int m_id = -1;

    for(int i = 0; i < n; i++) {
        int u = -1;
        ll cur = inf;

        for(int j = 0; j < n; j++) {
            if(vis[j]) continue;
            if(dist[j] < cur) {
                cur = dist[j];
                u = j;
            }

        }

        if(u == -1) break;

        vis[u] = 1;

        ll d = dist[u];


        for(int i : adj[u]) {
            if(block[i]) continue;
            int v = l[i] ^ r[i] ^ u;

            if(d + w[i] <= c[i]) {
                if(dist[v] > d + w[i]) {
                    dist[v] = d + w[i];
                    if(c[i] - dist[v] < mn) {
                        mn = c[i] - dist[v];
                        m_id = i;
                    }
                } 
            }
        }


    }


    return {mn, m_id};


}





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




    n = N;
    m = M;

    s = S;
    q = Q;



    for(int i = 0; i < M; i++) {
        adj[A[i]].push_back(i);
        adj[B[i]].push_back(i);
        l[i] = A[i];
        r[i] = B[i];

        c[i] = C[i];
        w[i] = L[i];

    }


    vector<int> con[n + 1];

    for(int i = 0; i < Q; i++) {
        q_t[i] = T[i];

        con[U[i]].push_back(i);
    }


    pii w0[n][n];

    for(int i = 0; i < n; i++) dijkstra1(i, w0[i]);

    vector<ll> res(Q);

    vector<int> ord(Q);
    iota(ord.begin(), ord.end(), 0);

    sort(ord.begin(), ord.end(), [](int a, int b) {
        return q_t[a] < q_t[b];
    });




    for(int u = 0; u < n; u++) {
        sort(con[u].begin(), con[u].end(), [](int a, int b) {
            return q_t[a] < q_t[b];
        });

        ll D[n];
        

        for(int j = 0; j < M; j++) block[j] = 0;


        auto [mn, id] = dijkstra2(u, D);



        for(int i : con[u]) {
            while(mn < T[i]) {
                block[id] = 1;
                auto [x, y] = dijkstra2(u, D);
                mn = x;
                id = y;
            }

            if(D[V[i]] != inf) res[i] = D[V[i]];
            else {
                res[i] = inf;
                for(int j = 0; j < n; j++) {
                    if(D[j] != inf) res[i] = min(res[i], S - T[i] + w0[j][V[i]].first * S + w0[j][V[i]].second);
                }
            }

        }

    }

    

    return res;



}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 135368 KB Output is correct
2 Correct 79 ms 135380 KB Output is correct
3 Correct 301 ms 135484 KB Output is correct
4 Correct 64 ms 135384 KB Output is correct
5 Correct 67 ms 135436 KB Output is correct
6 Correct 62 ms 135456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 200224 KB Output is correct
2 Correct 1609 ms 214204 KB Output is correct
3 Correct 1648 ms 205836 KB Output is correct
4 Correct 1583 ms 215376 KB Output is correct
5 Correct 1598 ms 215312 KB Output is correct
6 Correct 71 ms 135400 KB Output is correct
7 Correct 1588 ms 203848 KB Output is correct
8 Correct 1980 ms 227876 KB Output is correct
9 Correct 1437 ms 192176 KB Output is correct
10 Correct 1606 ms 214972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 135368 KB Output is correct
2 Correct 79 ms 135380 KB Output is correct
3 Correct 301 ms 135484 KB Output is correct
4 Correct 64 ms 135384 KB Output is correct
5 Correct 67 ms 135436 KB Output is correct
6 Correct 62 ms 135456 KB Output is correct
7 Correct 1458 ms 200224 KB Output is correct
8 Correct 1609 ms 214204 KB Output is correct
9 Correct 1648 ms 205836 KB Output is correct
10 Correct 1583 ms 215376 KB Output is correct
11 Correct 1598 ms 215312 KB Output is correct
12 Correct 71 ms 135400 KB Output is correct
13 Correct 1588 ms 203848 KB Output is correct
14 Correct 1980 ms 227876 KB Output is correct
15 Correct 1437 ms 192176 KB Output is correct
16 Correct 1606 ms 214972 KB Output is correct
17 Correct 1715 ms 248184 KB Output is correct
18 Correct 1680 ms 246840 KB Output is correct
19 Correct 1871 ms 272488 KB Output is correct
20 Correct 1790 ms 251280 KB Output is correct
21 Correct 1804 ms 280036 KB Output is correct
22 Correct 1876 ms 281052 KB Output is correct
23 Correct 1712 ms 250700 KB Output is correct
24 Correct 2091 ms 289748 KB Output is correct
25 Correct 1831 ms 239220 KB Output is correct
26 Correct 2001 ms 279552 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 135368 KB Output is correct
2 Correct 79 ms 135380 KB Output is correct
3 Correct 301 ms 135484 KB Output is correct
4 Correct 64 ms 135384 KB Output is correct
5 Correct 67 ms 135436 KB Output is correct
6 Correct 62 ms 135456 KB Output is correct
7 Correct 1458 ms 200224 KB Output is correct
8 Correct 1609 ms 214204 KB Output is correct
9 Correct 1648 ms 205836 KB Output is correct
10 Correct 1583 ms 215376 KB Output is correct
11 Correct 1598 ms 215312 KB Output is correct
12 Correct 71 ms 135400 KB Output is correct
13 Correct 1588 ms 203848 KB Output is correct
14 Correct 1980 ms 227876 KB Output is correct
15 Correct 1437 ms 192176 KB Output is correct
16 Correct 1606 ms 214972 KB Output is correct
17 Correct 1715 ms 248184 KB Output is correct
18 Correct 1680 ms 246840 KB Output is correct
19 Correct 1871 ms 272488 KB Output is correct
20 Correct 1790 ms 251280 KB Output is correct
21 Correct 1804 ms 280036 KB Output is correct
22 Correct 1876 ms 281052 KB Output is correct
23 Correct 1712 ms 250700 KB Output is correct
24 Correct 2091 ms 289748 KB Output is correct
25 Correct 1831 ms 239220 KB Output is correct
26 Correct 2001 ms 279552 KB Output is correct
27 Correct 3820 ms 249500 KB Output is correct
28 Correct 3909 ms 247748 KB Output is correct
29 Correct 4155 ms 267824 KB Output is correct
30 Correct 3568 ms 251228 KB Output is correct
31 Correct 4138 ms 276396 KB Output is correct
32 Correct 4163 ms 276248 KB Output is correct
33 Correct 2056 ms 288056 KB Output is correct
34 Correct 3814 ms 239060 KB Output is correct
35 Correct 3909 ms 277200 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 135368 KB Output is correct
2 Correct 79 ms 135380 KB Output is correct
3 Correct 301 ms 135484 KB Output is correct
4 Correct 64 ms 135384 KB Output is correct
5 Correct 67 ms 135436 KB Output is correct
6 Correct 62 ms 135456 KB Output is correct
7 Correct 1458 ms 200224 KB Output is correct
8 Correct 1609 ms 214204 KB Output is correct
9 Correct 1648 ms 205836 KB Output is correct
10 Correct 1583 ms 215376 KB Output is correct
11 Correct 1598 ms 215312 KB Output is correct
12 Correct 71 ms 135400 KB Output is correct
13 Correct 1588 ms 203848 KB Output is correct
14 Correct 1980 ms 227876 KB Output is correct
15 Correct 1437 ms 192176 KB Output is correct
16 Correct 1606 ms 214972 KB Output is correct
17 Correct 1715 ms 248184 KB Output is correct
18 Correct 1680 ms 246840 KB Output is correct
19 Correct 1871 ms 272488 KB Output is correct
20 Correct 1790 ms 251280 KB Output is correct
21 Correct 1804 ms 280036 KB Output is correct
22 Correct 1876 ms 281052 KB Output is correct
23 Correct 1712 ms 250700 KB Output is correct
24 Correct 2091 ms 289748 KB Output is correct
25 Correct 1831 ms 239220 KB Output is correct
26 Correct 2001 ms 279552 KB Output is correct
27 Correct 3820 ms 249500 KB Output is correct
28 Correct 3909 ms 247748 KB Output is correct
29 Correct 4155 ms 267824 KB Output is correct
30 Correct 3568 ms 251228 KB Output is correct
31 Correct 4138 ms 276396 KB Output is correct
32 Correct 4163 ms 276248 KB Output is correct
33 Correct 2056 ms 288056 KB Output is correct
34 Correct 3814 ms 239060 KB Output is correct
35 Correct 3909 ms 277200 KB Output is correct
36 Execution timed out 9018 ms 236688 KB Time limit exceeded
37 Halted 0 ms 0 KB -