Submission #298079

#	Time	Username	Problem	Language	Result	Execution time	Memory
298079		infinite_iq	Sky Walking (IOI19_walk)	C++14	10 / 100	51 ms	5728 KiB

walk

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

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43