Submission #298081

#	Time	Username	Problem	Language	Result	Execution time	Memory
298081		infinite_iq	Sky Walking (IOI19_walk)	C++14	10 / 100	4110 ms	445868 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[100009] ;
    int x [100009] , h [100009] ;
    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