Submission #709758

#	Time	Username	Problem	Language	Result	Execution time	Memory
709758		Jarif_Rahman	Escape Route (JOI21_escape_route)	C++17	5 / 100	9027 ms	280948 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll inf = 5e17;

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){

    vector<ll> ans(q, inf);
    vector<vector<tuple<int, ll, ll>>> v(n);
    
    for(int i = 0; i < m; i++){
        v[A[i]].pb({B[i], L[i], C[i]});
        v[B[i]].pb({A[i], L[i], C[i]});
    }

    vector<vector<ll>> dis2(n);

    for(int s = 0; s < n; s++){
        dis2[s].assign(n, inf);
        vector<bool> bl(n, 0);
        priority_queue<pair<ll, int>> pq;

        dis2[s][s] = 0;
        pq.push({0, s});

        while(!pq.empty()){
            int nd = pq.top().sc; pq.pop();
            if(bl[nd]) continue;
            bl[nd] = 1;

            for(auto [x, l, c]: v[nd])
                if((dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l) < dis2[s][x]){
                dis2[s][x] = (dis2[s][nd]%S+l<=c ? dis2[s][nd]+l:((dis2[s][nd]+S-1)/S)*S+l);
                pq.push({-dis2[s][x], x});
            }
        }
    }

    vector<vector<vector<ll>>> dis1;
    vector<ll> sth;
    ll t = 0;
    while(1){
        ll nxt = inf;
        sth.pb(t);
        dis1.pb(vector<vector<ll>>(n));
        vector<vector<ll>> &dis = dis1.back();
        for(int s = 0; s < n; s++){
            dis[s].assign(n, inf);
            vector<ll> change(n, inf);
            vector<bool> bl(n, 0);
            priority_queue<pair<ll, int>> pq;

            dis[s][s] = t;
            pq.push({0, s});

            while(!pq.empty()){
                int nd = pq.top().sc; pq.pop();
                if(bl[nd]) continue;
                bl[nd] = 1;

                for(auto [x, l, c]: v[nd]) if(dis[s][nd]+l <= min(dis[s][x]-1, c)){
                    dis[s][x] = dis[s][nd]+l;
                    change[x] = c-dis[s][x]+1;
                    pq.push({-dis[s][x], x});
                }
            }

            for(ll &x: dis[s]) if(x != inf) x-=t;
            nxt = min(nxt, *min_element(change.begin(), change.end()));
        }

        if(nxt == inf) break;
        t+=nxt;
    }

    for(int i = 0; i < q; i++){
        int p = (upper_bound(sth.begin(), sth.end(), T[i])-sth.begin())-1;
        if(dis1[p][U[i]][V[i]] != inf){
            ans[i] = min(ans[i], dis1[p][U[i]][V[i]]);
            continue;
        }
        for(int j = 0; j < n; j++) if(dis1[p][U[i]][j] != inf)
            ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]);
    }

    return ans;
}

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