oj.uz

Submission #31910

# Submission time Handle Problem Language Result Execution time Memory
31910 2017-09-14T09:39:20 Z chonka Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 2000 ms 105520 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 ( ) {
    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 29 ms 65392 KB Output is correct
2 Correct 0 ms 64864 KB Output is correct
3 Correct 0 ms 64864 KB Output is correct
4 Correct 9 ms 65260 KB Output is correct
5 Correct 6 ms 64996 KB Output is correct
6 Correct 0 ms 64864 KB Output is correct
7 Correct 0 ms 64864 KB Output is correct
8 Correct 0 ms 64864 KB Output is correct
9 Correct 0 ms 64864 KB Output is correct
10 Correct 3 ms 64996 KB Output is correct
11 Correct 3 ms 64996 KB Output is correct
12 Correct 9 ms 64996 KB Output is correct
13 Correct 6 ms 64996 KB Output is correct
14 Correct 3 ms 64996 KB Output is correct
15 Correct 26 ms 65392 KB Output is correct
16 Correct 26 ms 65392 KB Output is correct
17 Correct 23 ms 65392 KB Output is correct
18 Correct 13 ms 65260 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 64864 KB Output is correct
2 Correct 113 ms 67240 KB Output is correct
3 Correct 963 ms 94896 KB Output is correct
4 Correct 256 ms 71992 KB Output is correct
5 Correct 503 ms 76216 KB Output is correct
6 Correct 1973 ms 105520 KB Output is correct
7 Correct 6 ms 64864 KB Output is correct
8 Correct 3 ms 64864 KB Output is correct
9 Correct 3 ms 65000 KB Output is correct
10 Correct 0 ms 65000 KB Output is correct
11 Correct 3 ms 64864 KB Output is correct
12 Correct 0 ms 64864 KB Output is correct
13 Correct 119 ms 67240 KB Output is correct
14 Correct 56 ms 66580 KB Output is correct
15 Correct 59 ms 66712 KB Output is correct
16 Correct 49 ms 65656 KB Output is correct
17 Correct 329 ms 72520 KB Output is correct
18 Correct 273 ms 72388 KB Output is correct
19 Correct 229 ms 71992 KB Output is correct
20 Correct 176 ms 71464 KB Output is correct
21 Correct 479 ms 76612 KB Output is correct
22 Correct 533 ms 76216 KB Output is correct
23 Correct 629 ms 74368 KB Output is correct
24 Correct 446 ms 76612 KB Output is correct
25 Correct 1129 ms 94896 KB Output is correct
26 Correct 1193 ms 78064 KB Output is correct
27 Correct 1656 ms 96796 KB Output is correct
28 Execution timed out 2000 ms 105520 KB Execution timed out
29 Correct 1819 ms 104000 KB Output is correct
30 Correct 1759 ms 102744 KB Output is correct
31 Correct 1456 ms 77420 KB Output is correct
32 Correct 1496 ms 95812 KB Output is correct