Submission #422159

#	Time	Username	Problem	Language	Result	Execution time	Memory
422159		ioi	Tracks in the Snow (BOI13_tracks)	C++14	19.79 / 100	1951 ms	137556 KiB

tracks

#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)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: 6.666666666666667 / 30
• Subtask 2: 13.125 / 70