oj.uz

Submission #625108

# Submission time Handle Problem Language Result Execution time Memory
625108 2022-08-09T11:23:35 Z chonka Portals (BOI14_portals) C++17
31 / 100
 1000 ms 5488 KB 
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1007 ;

int dx[ 4 ] = { 1 , -1 , 0 , 0 } ;
int dy[ 4 ] = { 0 , 0 , 1 , -1 } ;

int n , m ;
string a[ MAXN ] ;
int aux[ MAXN ][ MAXN ] ;
int dist[ MAXN ][ MAXN ] ;

int up[ MAXN ][ MAXN ] , down[ MAXN ][ MAXN ] ;
int l[ MAXN ][ MAXN ] , r[ MAXN ][ MAXN ] ;


void solve ( ) {
    cin >> n >> m ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
        a[ i ] = '#' + a[ i ] ;
        a[ i ] += '#' ;
    }
    for ( int i = 0 ; i <= m + 1 ; ++ i ) {
        a[ 0 ] += '#' ;
        a[ n + 1 ] += '#' ;
    }
    queue < pair < int , int > > q ;
    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        for ( int j = 0 ; j <= m + 1 ; ++ j ) {
            if ( a[ i ][ j ] == '#' ) {
                q.push ( { i , j } ) ;
            }
        }
    }
    while ( q.empty ( ) == false ) {
        auto [ x , y ] = q.front ( ) ; q.pop ( ) ;
        for ( int i = 0 ; i < 4 ; ++ i ) {
            int nx = x + dx[ i ] , ny = y + dy[ i ] ;
            if ( nx < 0 || nx > n + 1 ) { continue ; }
            if ( ny < 0 || ny > m + 1 ) { continue ; }
            if ( a[ nx ][ ny ] == '#' ) { continue ; }
            if ( aux[ nx ][ ny ] == 0 ) {
                aux[ nx ][ ny ] = aux[ x ][ y ] + 1 ;
                q.push ( { nx , ny } ) ;
            }
        }
    }

    priority_queue < pair < int , pair < int , int > > > pq ;

    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        for ( int j = 0 ; j <= m + 1 ; ++ j ) {
            if ( a[ i ][ j ] == '#' ) {
                up[ i ][ j ] = i ;
                l[ i ][ j ] = j ;
            }
            else {
                up[ i ][ j ] = up[ i - 1 ][ j ] ;
                l[ i ][ j ] = l[ i ][ j - 1 ] ;
            }
        }
    }
    for ( int i = n + 1 ; i >= 0 ; -- i ) {
        for ( int j = m + 1 ; j >= 0 ; -- j ) {
            if ( a[ i ][ j ] == '#' ) {
                down[ i ][ j ] = i ;
                r[ i ][ j ] = j ;
            }
            else {
                down[ i ][ j ] = down[ i + 1 ][ j ] ;
                r[ i ][ j ] = r[ i ][ j + 1 ] ;
            }
        }
    }

    
    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        for ( int j = 0 ; j <= m + 1 ; ++ j ) {
            dist[ i ][ j ] = MAXN * MAXN ; 
            if ( a[ i ][ j ] == 'S' ) {
                dist[ i ][ j ] = 0 ;
                pq.push ( make_pair ( 0 , make_pair ( i , j ) ) ) ;
            }
        }
    }
    while ( pq.empty ( ) == false ) {
        auto hh = pq.top ( ) ;
        int c = hh.first , x = hh.second.first , y = hh.second.second ;
        pq.pop ( ) ;
        if ( c != dist[ x ][ y ] ) { continue ; }
        for ( int i = 0 ; i < 4 ; ++ i ) {
            int nx = x + dx[ i ] , ny = y + dy[ i ] ;
            if ( nx < 0 || nx > n + 1 ) { continue ; }
            if ( ny < 0 || ny > m + 1 ) { continue ; }
            if ( a[ nx ][ ny ] == '#' ) { continue ; }
            if ( dist[ nx ][ ny ] > c + 1 ) {
                dist[ nx ][ ny ] = c + 1 ;
                pq.push ( make_pair ( c + 1 , make_pair ( nx , ny ) ) ) ;
            }
        }
        for ( auto nx : { up[ x ][ y ] + 1 , down[ x ][ y ] - 1 } ) {
            int len = c + aux[ x ][ y ] ;
            if ( dist[ nx ][ y ] > len ) {
                dist[ nx ][ y ] = len ;
                pq.push ( make_pair ( len , make_pair ( nx , y ) ) ) ;
            }
        }
        for ( auto ny : { l[ x ][ y ] + 1 , r[ x ][ y ] - 1 } ) {
            int len = c + aux[ x ][ y ] ;
            if ( dist[ x ][ ny ] > len ) {
                dist[ x ][ ny ] = len ;
                pq.push ( make_pair ( len , make_pair ( x , ny ) ) ) ;
            }
        }
    }
    for ( int i = 0 ; i <= n + 1 ; ++ i ) {
        for ( int j = 0 ; j <= m + 1 ; ++ j ) {
            if ( a[ i ][ j ] == 'C' ) {
                cout << dist[ i ][ j ] << "\n" ;
                return ;
            }
        }
    }    
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 616 KB Output is correct
3 Correct 1 ms 616 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 596 KB Output is correct
8 Correct 1 ms 616 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 616 KB Output is correct
3 Correct 1 ms 616 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 612 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 66 ms 1620 KB Output is correct
10 Correct 45 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 20 ms 1628 KB Output is correct
13 Correct 37 ms 1620 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 20 ms 1640 KB Output is correct
16 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 612 KB Output is correct
5 Correct 38 ms 5460 KB Output is correct
6 Execution timed out 1079 ms 5488 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 0 ms 616 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 616 KB Output is correct
9 Correct 65 ms 1620 KB Output is correct
10 Correct 37 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 16 ms 1620 KB Output is correct
13 Correct 37 ms 1620 KB Output is correct
14 Correct 37 ms 5460 KB Output is correct
15 Execution timed out 1080 ms 5460 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 616 KB Output is correct
4 Correct 1 ms 488 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 66 ms 1620 KB Output is correct
10 Correct 38 ms 1620 KB Output is correct
11 Correct 2 ms 1620 KB Output is correct
12 Correct 15 ms 1620 KB Output is correct
13 Correct 36 ms 1620 KB Output is correct
14 Correct 37 ms 5476 KB Output is correct
15 Execution timed out 1078 ms 5460 KB Time limit exceeded
16 Halted 0 ms 0 KB -