Submission #625108

#	Time	Username	Problem	Language	Result	Execution time	Memory
625108		chonka	Portals (BOI14_portals)	C++17	31 / 100	1080 ms	5488 KiB

portals

#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 / 11
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30