oj.uz

Submission #31911

# Submission time Handle Problem Language Result Execution time Memory
31911 2017-09-14T09:40:24 Z chonka Tracks in the Snow (BOI13_tracks) C++
100 / 100
 1493 ms 104988 KB 
#include<iostream>
#include<stdio.h>
#include<string>
#include<queue>
using namespace std ;

#define MAXN 4007

int n , m ;
string a[ MAXN ] ;

int used[ MAXN ][ MAXN ] ;
int ans = 0 ;

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

void bfs ( ) {
    queue < pair < int , int > > q ;
    queue < pair < int , int > > aux ;
    int i , j ;
    used[ n ][ m ] = 1 ;
    q.push ( make_pair ( n , m ) ) ;
    while ( 1 ) {
        ans ++ ;
        while ( q.empty ( ) == false ) {
            pair < int , int > p = q.front ( ) ;
            q.pop ( ) ;
            int i ;
            for ( i = 0 ; i < 4 ; i ++ ) {
                int nx , ny ;
                nx = p.first + dx[ i ] ;
                ny = p.second + dy[ i ] ;
                if ( nx < 1 || n < nx ) { continue ; }
                if ( ny < 1 || m < ny ) { continue ; }
                if ( a[ nx ][ ny ] == '.' ) { continue ; }
                if ( used[ nx ][ ny ] != 0 ) { continue ; }
                used[ nx ][ ny ] = used[ p.first ][ p.second ] + 1 ;
                if ( a[ nx ][ ny ] == a[ p.first ][ p.second ] ) {
                    q.push ( make_pair ( nx , ny ) ) ;
                }
                else {
                    aux.push ( make_pair ( nx , ny ) ) ;
                }
            }
        }
        if ( aux.empty ( ) == true ) { break ; }
        while ( aux.empty ( ) == false ) {
            q.push ( aux.front ( ) ) ;
            aux.pop ( ) ;
        }
    }
}

void input ( ) {
    cin >> n >> m ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        cin >> a[ i ] ;
        a[ i ] = '#' + a[ i ] ;
    }
}

void solve ( ) {
    bfs ( ) ;
    printf ( "%d\n" , ans ) ;
}


int main ( ) {
    ios_base::sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

tracks.cpp: In function 'void bfs()':
tracks.cpp:21:9: warning: unused variable 'i' [-Wunused-variable]
     int i , j ;
         ^
tracks.cpp:21:13: warning: unused variable 'j' [-Wunused-variable]
     int i , j ;
             ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 65552 KB Output is correct
2 Correct 0 ms 65024 KB Output is correct
3 Correct 0 ms 65024 KB Output is correct
4 Correct 6 ms 65420 KB Output is correct
5 Correct 0 ms 65156 KB Output is correct
6 Correct 0 ms 65024 KB Output is correct
7 Correct 0 ms 65024 KB Output is correct
8 Correct 0 ms 65024 KB Output is correct
9 Correct 0 ms 65024 KB Output is correct
10 Correct 3 ms 65156 KB Output is correct
11 Correct 0 ms 65156 KB Output is correct
12 Correct 3 ms 65156 KB Output is correct
13 Correct 3 ms 65156 KB Output is correct
14 Correct 3 ms 65156 KB Output is correct
15 Correct 13 ms 65552 KB Output is correct
16 Correct 16 ms 65552 KB Output is correct
17 Correct 9 ms 65420 KB Output is correct
18 Correct 9 ms 65420 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 65024 KB Output is correct
2 Correct 63 ms 68060 KB Output is correct
3 Correct 246 ms 94384 KB Output is correct
4 Correct 96 ms 72152 KB Output is correct
5 Correct 149 ms 81820 KB Output is correct
6 Correct 1319 ms 104988 KB Output is correct
7 Correct 6 ms 65024 KB Output is correct
8 Correct 3 ms 65024 KB Output is correct
9 Correct 0 ms 65160 KB Output is correct
10 Correct 0 ms 65024 KB Output is correct
11 Correct 3 ms 65024 KB Output is correct
12 Correct 0 ms 65024 KB Output is correct
13 Correct 63 ms 68060 KB Output is correct
14 Correct 29 ms 66740 KB Output is correct
15 Correct 26 ms 66872 KB Output is correct
16 Correct 29 ms 66212 KB Output is correct
17 Correct 189 ms 72680 KB Output is correct
18 Correct 126 ms 72548 KB Output is correct
19 Correct 106 ms 72152 KB Output is correct
20 Correct 59 ms 71492 KB Output is correct
21 Correct 183 ms 82340 KB Output is correct
22 Correct 146 ms 81820 KB Output is correct
23 Correct 416 ms 80184 KB Output is correct
24 Correct 139 ms 82796 KB Output is correct
25 Correct 583 ms 94384 KB Output is correct
26 Correct 856 ms 87736 KB Output is correct
27 Correct 1096 ms 96260 KB Output is correct
28 Correct 1389 ms 104988 KB Output is correct
29 Correct 1493 ms 103464 KB Output is correct
30 Correct 1296 ms 102184 KB Output is correct
31 Correct 1249 ms 84932 KB Output is correct
32 Correct 849 ms 95168 KB Output is correct