Submission #917936

#	Time	Username	Problem	Language	Result	Execution time	Memory
917936		Equinox	Escape Route (JOI21_escape_route)	C++17	5 / 100	9037 ms	154960 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
//typedef complex<double> cpx;
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define compress(x) x.erase(unique(all(x)),x.end())
#define ff first
#define ss second
#define INF 1e17
#define MAX 500010
#define SIZE 10010
#define MOD 1000000007

struct edge{
    ll x,w,c;
};

ll n,m,s,q,dist[100];
vector<edge> g[100];

void dijkstra(ll u, ll t){
    for(int i=1;i<=n;i++){
        dist[i] = (ll)1e18;
    }
    dist[u] = 0;
    priority_queue<pll> pq;
    pq.push({0,u});
    while(!pq.empty()){
        ll cur = pq.top().ss, len = -pq.top().ff;
        pq.pop();
        if(dist[cur]<len) continue;
        for(auto i:g[cur]){
            ll nx = i.x, l = i.w, c = i.c;
            ll w = l;
            if((len+t)%s>c-l) w += (s-(len+t)%s);
            if(len+w<dist[nx]){
                dist[nx] = len+w;
                pq.push({-dist[nx],nx});
            }
        }
    }
}

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

    n = N; m = M; q = Q; s = S;
    for(int i=0;i<m;i++){
        g[A[i]+1].push_back({B[i]+1,L[i],C[i]});
        g[B[i]+1].push_back({A[i]+1,L[i],C[i]});
    }

    vector<ll> ans;
    for(int i=0;i<q;i++){
        ll u = U[i]+1, v = V[i]+1, t = T[i];
        dijkstra(u,t);
        ans.push_back(dist[v]);
    }

    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 10
• Subtask 4: 0 / 35
• Subtask 5: 0 / 30