oj.uz

Submission #422013

# Submission time Handle Problem Language Result Execution time Memory
422013 2021-06-09T14:48:07 Z tqbfjotld Escape Route (JOI21_escape_route) C++17
5 / 100
 9000 ms 112004 KB 
#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<pair<int,int>,int> > adjl[99];

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

    for (int x = 0; x<M; x++){
        if (L[x]>C[x]) continue;
        adjl[A[x]].push_back({{L[x],C[x]},B[x]});
        adjl[B[x]].push_back({{L[x],C[x]},A[x]});
    }
    vector<int> ans;
    for (int x = 0; x<Q; x++){
        int dist[99];
        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
        for (int y = 0; y<N; y++){
            dist[y] = 999999999999999999LL;
        }
        dist[U[x]] = T[x];
        pq.push({dist[U[x]],U[x]});
        while (!pq.empty()){
            int node = pq.top().second;
            int d = pq.top().first;
            pq.pop();
            if (d>dist[node]) continue;
           // printf("node %lld dist %lld\n",node,d);
            for (auto x : adjl[node]){
                int nxd;
                if (d%S+x.first.first>x.first.second){
                     nxd = ((d/S)+1)*S+x.first.first;
                }else{
                    nxd = d+x.first.first;
                }
                if (nxd<dist[x.second]){
                    dist[x.second] = nxd;
                    pq.push({nxd,x.second});
                }
            }
        }
        ans.push_back(dist[V[x]]-T[x]);
    }

  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64972 KB Output is correct
2 Correct 36 ms 64980 KB Output is correct
3 Correct 45 ms 65024 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 38 ms 64972 KB Output is correct
6 Correct 29 ms 64964 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64972 KB Output is correct
2 Correct 36 ms 64980 KB Output is correct
3 Correct 45 ms 65024 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 38 ms 64972 KB Output is correct
6 Correct 29 ms 64964 KB Output is correct
7 Execution timed out 9008 ms 112004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64972 KB Output is correct
2 Correct 36 ms 64980 KB Output is correct
3 Correct 45 ms 65024 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 38 ms 64972 KB Output is correct
6 Correct 29 ms 64964 KB Output is correct
7 Execution timed out 9008 ms 112004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 64972 KB Output is correct
2 Correct 36 ms 64980 KB Output is correct
3 Correct 45 ms 65024 KB Output is correct
4 Correct 32 ms 64964 KB Output is correct
5 Correct 38 ms 64972 KB Output is correct
6 Correct 29 ms 64964 KB Output is correct
7 Execution timed out 9008 ms 112004 KB Time limit exceeded
8 Halted 0 ms 0 KB -