제출 #583391

#제출 시각아이디문제언어결과실행 시간메모리
583391alireza_kavianiEscape Route (JOI21_escape_route)C++17
0 / 100
9009 ms112252 KiB
#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} , -MAXN}; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...