oj.uz

Submission #532775

# Submission time Handle Problem Language Result Execution time Memory
532775 2022-03-03T21:00:17 Z nafis_shifat Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 119460 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 = 3e5 + 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 dijkstra(int source, int target, ll t) {
    int vis[n + 1] = {};
    pii dist[n + 1];

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


    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 == target) {
            ll res = s * dist[target].first + dist[target].second;
            return res - t;
        }

        if(u == -1) assert(0);

        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]});
        }


    }

    assert(0);

    return -1;


}

/*
ll dijkstra(int source, int target, ll t) {
    priority_queue <tuple<ll, ll, int>, vector<tuple<ll, ll, int>>, greater<tuple<ll, ll, int>> > pq;
    pq.push({0, t, source});

    int vis[n + 1][2] = {};

    pii dist[n + 1];

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

    dist[source] = {0, t};

    while(!pq.empty()) {
        auto [d, T, u] = pq.top();
        pq.pop();

        if(T > 0 && vis[u][1]) continue;
        if(T == 0 && vis[u][0]) continue;


        if(T == 0) vis[u][0] = 1;
        else vis[u][1] = 1;


        pq.push({d + 1, 0, u});


        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]);
                    pq.push({d, T + w[i], v});
                } 

            }
        }

    }


    ll res = s * dist[target].first + dist[target].second;

    return res - t;

}
*/
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<ll> res(Q);

    for(int i = 0; i < Q; i++) {

        res[i] = dijkstra(U[i], V[i], T[i]);
    }

    return res;



}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72012 KB Output is correct
2 Correct 33 ms 72044 KB Output is correct
3 Correct 40 ms 72112 KB Output is correct
4 Correct 27 ms 72012 KB Output is correct
5 Correct 35 ms 72104 KB Output is correct
6 Correct 30 ms 72012 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9077 ms 119460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72012 KB Output is correct
2 Correct 33 ms 72044 KB Output is correct
3 Correct 40 ms 72112 KB Output is correct
4 Correct 27 ms 72012 KB Output is correct
5 Correct 35 ms 72104 KB Output is correct
6 Correct 30 ms 72012 KB Output is correct
7 Execution timed out 9077 ms 119460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72012 KB Output is correct
2 Correct 33 ms 72044 KB Output is correct
3 Correct 40 ms 72112 KB Output is correct
4 Correct 27 ms 72012 KB Output is correct
5 Correct 35 ms 72104 KB Output is correct
6 Correct 30 ms 72012 KB Output is correct
7 Execution timed out 9077 ms 119460 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72012 KB Output is correct
2 Correct 33 ms 72044 KB Output is correct
3 Correct 40 ms 72112 KB Output is correct
4 Correct 27 ms 72012 KB Output is correct
5 Correct 35 ms 72104 KB Output is correct
6 Correct 30 ms 72012 KB Output is correct
7 Execution timed out 9077 ms 119460 KB Time limit exceeded
8 Halted 0 ms 0 KB -