Submission #583377

#	Time	Username	Problem	Language	Result	Execution time	Memory
583377		alireza_kaviani	Escape Route (JOI21_escape_route)	C++17	0 / 100	9075 ms	112216 KiB

escape_route

#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)  (x).begin(), (x).end()
#define SZ(x)   ll((x).size())
#define X       first
#define Y       second
#define sep     ' '

const ll MAXN = 100;
const ll INF = 8e18;

ll n , m , s , q , dist[MAXN] , mark[MAXN] , l[MAXN][MAXN] , c[MAXN][MAXN] , res[MAXN * MAXN][MAXN] , flag[MAXN * MAXN][MAXN];
vector<pair<pll , int>> vec[MAXN][MAXN];

void solve_suffix(int v , ll x , int ind){
    fill(mark , mark + MAXN , 0);
    fill(dist , dist + MAXN , INF);
    dist[v] = x;
    for(int i = 0 ; i < n ; i++){
        int mn = -1;
        for(int j = 0 ; j < n ; j++){
            if(mark[j]) continue;
            if(mn == -1 || dist[j] < dist[mn]){
                mn = j;
            }
        }
        int v = mn;
        mark[v] = 1;
        for(int u = 0 ; u < n ; u++){
            if(dist[v] % s <= c[v][u]){
                dist[u] = min(dist[u] , dist[v] + l[v][u]);
            }
            else{
                dist[u] = min(dist[u] , dist[v] + s - dist[v] % s + l[v][u]);
            }
        }
    }
    for(int i = 0 ; i < n ; i++){
        res[ind][i] = dist[i] - x;
        if(dist[i] >= s){
            flag[ind][i] = 1;
        }
    }
}

void solve_prefix(int v , ll x , int ind){
    fill(mark , mark + MAXN , 0);
    fill(dist , dist + MAXN , -INF);
    dist[v] = x;
    for(int i = 0 ; i < n ; i++){
        int mx = -1;
        for(int j = 0 ; j < n ; j++){
            if(mark[j]) continue;
            if(mx == -1 || dist[j] > dist[mx]){
                mx = j;
            }
        }
        int v = mx;
        mark[v] = 1;
        for(int u = 0 ; u < n ; u++){
            dist[u] = max(dist[u] , min(dist[v] - l[v][u] , c[v][u]));
        }
    }
    for(int i = 0 ; i < n ; i++){
        vec[i][v].push_back({{dist[i] , x - dist[i]} , ind});
    }
}

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) {
    
    for(int i = 0 ; i < MAXN ; i++){
        fill(l[i] , l[i] + MAXN , INF);
    }

    n = N; m = M; s = S; q = Q;
    for(int i = 0 ; i < m ; i++){
        int v = A[i] , u = B[i];
        l[v][u] = l[u][v] = L[i];
        c[v][u] = c[u][v] = C[i] - L[i];
    }
    for(int i = 0 ; i < m ; i++){
        solve_suffix(B[i] , C[i] , i * 2);
        solve_suffix(A[i] , C[i] , i * 2 + 1);
    }
    for(int i = 0 ; i < n ; i++){
        solve_suffix(i , 0 , m * 2 + i);
    }
    for(int i = 0 ; i < m ; i++){
        solve_prefix(B[i] , C[i] , i * 2);
        solve_prefix(A[i] , C[i] , i * 2 + 1);
    }
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            sort(all(vec[i][j]));
            for(int k = SZ(vec[i][j]) - 2 ; k >= 0 ; k--){
                vec[i][j][k].X.Y = min(vec[i][j][k].X.Y, vec[i][j][k + 1].X.Y);
            }
        }
    }
    vector<ll> ans;
    for(int i = 0 ; i < q ; i++){
        ll v = U[i] , u = V[i] , t = T[i];
        pair<pll , int> lb = {{t , -INF} , -INF};
        ll cur = res[m * 2 + v][u] + s - t;
        for(int j = 0 ; j < m * 2 ; j++){
            int ind = lower_bound(all(vec[v][j]) , lb) - vec[v][j].begin();
            if(ind == SZ(vec[v][j]))  continue;
            int E = vec[v][j][ind].Y;
            ll val = vec[v][j][ind].X.Y + res[E][u];
            if(flag[E][u] == 0){
                cur = min(cur , val);
                continue;
            }
            val = C[E / 2] - t + res[E][u];
            cur = min(cur , val);
        }
        ans.push_back(cur);
    }
    return ans;
}

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