Submission #709830

#	Time	Username	Problem	Language	Result	Execution time	Memory
709830		Jarif_Rahman	Escape Route (JOI21_escape_route)	C++17	35 / 100	9015 ms	147580 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;
const int N = 90;
vector<tuple<int, ll, ll>> v[N];
bitset<N> bl;
priority_queue<pair<ll, int>> pq;

ll dis2[N][N];
ll dis[N];

vector<int> Q[N];

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

    for(int i = 0; i < q; i++){
        Q[U[i]].pb(i);
    }
    for(int i = 0; i < n; i++){
        sort(Q[i].begin(), Q[i].end(), [&](int a, int b){
            return T[a] < T[b];
        });
    }

    for(int s = 0; s < n; s++){
        fill(dis2[s], dis2[s]+n, inf);
        for(int i = 0; i < n; i++) bl[i] = 0;

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

    bl.reset();
    bl.flip();
    for(int s = 0; s < n; s++){
        ll t = S;
        priority_queue<tuple<ll, int, ll>> sth;
        sth.push({S, s, 0});
        fill(dis, dis+n, inf);

        while(!Q[s].empty()){
            while(!sth.empty() && get<0>(sth.top()) == t){
                auto [ig, x, w] = sth.top(); sth.pop();
                dis[x] = min(dis[x], w);
                pq.push({-dis[x], x});
                bl[x] = 0;
            }

            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[nd]+l < dis[x]){
                    if(dis[nd]+l <= c-t){
                        dis[x] = dis[nd]+l;
                        pq.push({-dis[x], x});
                        bl[x] = 0;
                    }
                    else{
                        sth.push({c-dis[nd]-l, x, dis[nd]+l});
                    }
                }
            }

            if(!sth.empty()) t = get<0>(sth.top());
            else t = -inf;

            while(!Q[s].empty() && T[Q[s].back()] > t){
                int i = Q[s].back();
                Q[s].pop_back();
                if(dis[V[i]] != inf){
                    ans[i] = min(ans[i], dis[V[i]]);
                    continue;
                }
                for(int j = 0; j < n; j++) if(dis[j] != inf)
                    ans[i] = min(ans[i], S-T[i]+dis2[j][V[i]]);
            }

            if(t < 0) break;
        }
    }

    return ans;
}

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