oj.uz

Submission #422161

# Submission time Handle Problem Language Result Execution time Memory
422161 2021-06-09T19:43:11 Z ioi Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1643 ms 122984 KB 
#include<bits/stdc++.h>
using namespace std ;


int h , w ;
char arr[4010][4010];
int dis[4010][4010];
int ans = 0 ;
pair<int , int > cor [] = {{1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}} ;

void bfs(){

    deque<pair<int , int > > d ;

    dis[0][0] = 1 ;
    d.push_back({0 , 0});

    while(d.size()){


        auto fr = d.front();
        d.pop_front();

        ans = max(ans , dis[fr.first][fr.second]);


        for(int ii = 0 ; ii < 4 ; ii ++){

            int nx = cor[ii].first + fr.first ;
            int ny = cor[ii].second + fr.second ;
            int x = fr.first , y = fr.second ;
            if(nx < 0 || ny < 0 || nx >= h || ny >= w || arr[nx][ny] == '.')continue ;
            int w = arr[x][y] != arr[nx][ny];

            if(dis[nx][ny] > dis[x][y] + w){

                dis[nx][ny] = dis[x][y] + w ;

                if(w)d.push_back({nx , ny});
                else d.push_front({nx , ny});


            }

        }



    }


}
int main(){

    cin >> h >> w ;




    for(int i = 0 ; i < h ; i ++)
        for(int j = 0 ;j < w ; j ++){
            cin >> arr[i][j];
            dis[i][j] = 1e9 ;

        }


    bfs();


    cout << ans ;



}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5416 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 17 ms 5048 KB Output is correct
5 Correct 8 ms 2880 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 680 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 2 ms 1068 KB Output is correct
10 Correct 7 ms 2508 KB Output is correct
11 Correct 6 ms 2144 KB Output is correct
12 Correct 10 ms 3068 KB Output is correct
13 Correct 8 ms 2892 KB Output is correct
14 Correct 8 ms 2996 KB Output is correct
15 Correct 26 ms 5440 KB Output is correct
16 Correct 27 ms 5324 KB Output is correct
17 Correct 27 ms 5196 KB Output is correct
18 Correct 19 ms 5068 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 30848 KB Output is correct
2 Correct 133 ms 17744 KB Output is correct
3 Correct 1157 ms 83456 KB Output is correct
4 Correct 301 ms 33560 KB Output is correct
5 Correct 722 ms 63948 KB Output is correct
6 Correct 1561 ms 97212 KB Output is correct
7 Correct 17 ms 32212 KB Output is correct
8 Correct 18 ms 30828 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 440 KB Output is correct
11 Correct 18 ms 31684 KB Output is correct
12 Correct 3 ms 1612 KB Output is correct
13 Correct 131 ms 17808 KB Output is correct
14 Correct 88 ms 11836 KB Output is correct
15 Correct 79 ms 13036 KB Output is correct
16 Correct 62 ms 6532 KB Output is correct
17 Correct 340 ms 36032 KB Output is correct
18 Correct 321 ms 35636 KB Output is correct
19 Correct 299 ms 33556 KB Output is correct
20 Correct 269 ms 30976 KB Output is correct
21 Correct 703 ms 65884 KB Output is correct
22 Correct 694 ms 63820 KB Output is correct
23 Correct 651 ms 54152 KB Output is correct
24 Correct 700 ms 65156 KB Output is correct
25 Correct 1428 ms 82820 KB Output is correct
26 Correct 1121 ms 122984 KB Output is correct
27 Correct 1540 ms 109248 KB Output is correct
28 Correct 1643 ms 96344 KB Output is correct
29 Correct 1547 ms 94276 KB Output is correct
30 Correct 1587 ms 98264 KB Output is correct
31 Correct 1071 ms 67016 KB Output is correct
32 Correct 1360 ms 96676 KB Output is correct