Submission #58746

#	Time	Username	Problem	Language	Result	Execution time	Memory
58746		Batrr	Tracks in the Snow (BOI13_tracks)	C++14	93.44 / 100	2075 ms	264100 KiB

tracks

#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=1e7+12,LOG=20;

int n,m,ans;
pair<int,int> dir[]={{0,-1},{-1,0},{1,0},{0,1}};
bool was[4001][4001];
string s[4001];
bool check(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || s[x][y]=='.')
        return 0;
     return 1;
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>s[i];
    queue< pair<int,int> > q1,q2;
    q1.push({0,0});
    was[0][0]=1;
    while(true){
        
        while(!q1.empty()){
            int x=q1.front().f,y=q1.front().s;
            //cout<<x<<" "<<y<<endl;
            q1.pop();
            for(int i=0;i<4;i++){
                int nx=x+dir[i].f,ny=y+dir[i].s;
                if( check(nx,ny) && !was[nx][ny] ){     
                    if(s[x][y]==s[nx][ny])
                        q1.push({nx,ny});
                     else
                        q2.push({nx,ny});             
                    was[nx][ny]=1;
                }
            }
        }
        ans++;
        if(q2.empty())
            break;
        swap(q1,q2);
    }            
    cout<<ans;
}

• Subtask 1: 30 / 30
• Subtask 2: 63.4375 / 70