Submission #422013

#	Time	Username	Problem	Language	Result	Execution time	Memory
422013		tqbfjotld	Escape Route (JOI21_escape_route)	C++17	5 / 100	9008 ms	112004 KiB

escape_route

#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 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30