oj.uz

Submission #298081

# Submission time Handle Problem Language Result Execution time Memory
298081 2020-09-12T11:19:01 Z infinite_iq Sky Walking (IOI19_walk) C++14
10 / 100
 4000 ms 445868 KB 
    #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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 5 ms 2944 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 ms 2688 KB Output is correct
16 Correct 3 ms 2688 KB Output is correct
17 Correct 5 ms 2944 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Execution timed out 4085 ms 184480 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 26104 KB Output is correct
2 Execution timed out 4110 ms 445868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 26104 KB Output is correct
2 Execution timed out 4110 ms 445868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 4 ms 2816 KB Output is correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 5 ms 2944 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 3 ms 2688 KB Output is correct
15 Correct 3 ms 2688 KB Output is correct
16 Correct 3 ms 2688 KB Output is correct
17 Correct 5 ms 2944 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2688 KB Output is correct
20 Execution timed out 4085 ms 184480 KB Time limit exceeded
21 Halted 0 ms 0 KB -