oj.uz

Submission #532922

# Submission time Handle Problem Language Result Execution time Memory
532922 2022-03-04T08:37:18 Z nafis_shifat Escape Route (JOI21_escape_route) C++17
20 / 100
 1351 ms 288504 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];

    }

    for(int i = 0; i < Q; i++) q_t[i] = T[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];
    });

    ll D[n];

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

    for(int i : ord) {

        while(mn < T[i]) {
            block[id] = 1;
            auto [x, y] = dijkstra2(U[i], 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 135364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 199880 KB Output is correct
2 Correct 1214 ms 266240 KB Output is correct
3 Correct 1155 ms 247392 KB Output is correct
4 Correct 1049 ms 275784 KB Output is correct
5 Correct 1008 ms 276012 KB Output is correct
6 Correct 59 ms 135344 KB Output is correct
7 Correct 947 ms 246840 KB Output is correct
8 Correct 1351 ms 288504 KB Output is correct
9 Correct 886 ms 235084 KB Output is correct
10 Correct 990 ms 275664 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 135364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 135364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 135364 KB Output isn't correct
2 Halted 0 ms 0 KB -