이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std ;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ins insert
#define era erase
#define C continue
typedef long long ll ;
typedef pair < int , int > pi ;
typedef vector < int > vi ;
typedef vector < pi > vpi ;
#include "walk.h"
int n , m ;
vi Sky[59] ;
int x [59] , h [59] ;
map < pi , vector < pair < pi , int > > > v ;
map < pi , ll > dis , done ;
void solve ( pi st ) {
set < pair < ll , pi > > s ;
s .ins ( { 0 , st } ) ;
while ( s .size () ) {
pair < ll , pi > ret = * s .begin () ;
s .era ( s .begin () ) ;
done [ret.se] = 1 ;
for ( auto u : v [ret.se] ) {
if ( done [u.fi] ) C ;
if ( s .find ( { dis [u.fi] , u .fi } ) != s .end () ) {
s .era ( { dis [u.fi] , u .fi } ) ;
}
if ( dis [u.fi] == 0 ) dis [u.fi] = (ll)1e18 ;
dis [u.fi] = min ( dis [u.fi] , (ll)(u.se + ret .fi) ) ;
s .ins ( { dis [u.fi] , u .fi } ) ;
}
}
}
long long min_distance ( vi X , vi H , vi L , vi R , vi Y , int s , int g ) {
n = X .size () , m = L .size () ;
if ( s > g ) swap ( s , g ) ;
for ( int i = 0 ; i < n ; i ++ ) {
x [i] = X [i] ;
h [i] = H [i] ;
Sky [i] .pb ( 0 ) ;
}
for ( int i = 0 ; i < m ; i ++ ) {
int l = L [i] , r = R [i] , y = Y [i] ;
for ( int j = l ; j <= r ; j ++ ) {
if ( h [j] >= y ) {
Sky [j] .pb ( y ) ;
}
}
int last = x [l] ;
for ( int j = l + 1 ; j <= r ; j ++ ) {
if ( h [j] >= y ) {
v [ mp ( last , y ) ] .pb ( { mp ( x [j] , y ) , x [j] - last } ) ;
v [ mp ( x [j] , y) ] .pb ( { mp ( last , y ) , x [j] - last } ) ;
last = x [j] ;
}
}
}
for ( int i = 0 ; i < n ; i ++ ) {
sort ( Sky [i] .begin () , Sky [i] .end () ) ;
for ( int j = 1 ; j < (int) Sky [i] .size () ; j ++ ) {
v [ mp ( x [i] , Sky [i][j-1] ) ] .pb ( { mp ( x [i] , Sky [i][j] ) , Sky [i][j] - Sky [i][j-1] } ) ;
}
reverse ( Sky [i] .begin () , Sky [i] .end () ) ;
for ( int j = 1 ; j < (int) Sky [i] .size () ; j ++ ) {
v [ mp ( x [i] , Sky [i][j-1] ) ] .pb ( { mp ( x [i] , Sky [i][j] ) , Sky [i][j-1] - Sky [i][j] } ) ;
}
}
solve ( { x [s] , 0 } ) ;
return ( dis [ mp ( x [g] , 0 ) ] == 0 ? -1 : dis [ mp ( x [g] , 0 ) ] ) ;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |