Submission #1277042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277042		deepanshusau	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1131 ms	406428 KiB

tracks

// deepanshusau

#pragma GCC optimize ("O3")

#ifdef ONPC
#define _GLIBCXX_DEBUG
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(arr,n)
#endif

#include<bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define pii pair<int, int> 
#define vi vector<int>
#define F first
#define S second
#define pb push_back
#define PI acos(-1)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define int long long

constexpr char sp=' ';
constexpr char nl='\n';
constexpr int MOD=1e9+7;

void solve(){
    int n,m;cin>>n>>m;
    vector<string> g(n);
    for(int i=0;i<n;i++) cin>>g[i];
        
    int ans=0;
    vi row={0,0,1,-1},col={1,-1,0,0};
    vector<vi> dis(n,vi(m,1)),vis(n,vi(m,0));
    deque<pii> dq;
    dq.push_back({0,0});
    while(sz(dq)){
        auto [i,j]=dq.front();
        dq.pop_front();
        vis[i][j]=1;
        ans=max(ans,dis[i][j]);
        for(int k=0;k<4;k++){
            int x=i+row[k],y=j+col[k];
            if(x>=0 && x<n && y>=0 && y<m && vis[x][y]==0 && g[x][y]!='.'){
                if(g[x][y]==g[i][j]){
                    dis[x][y]=dis[i][j];
                    dq.push_front({x,y});
                }
                else{
                    dis[x][y]=dis[i][j]+1;
                    dq.push_back({x,y});
                }
            }
        }
    }
    
    cout<<ans<<nl;
}

signed main(){

    clock_t tStart = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(12) << fixed;

    #ifdef ONPC
    freopen("debug.txt", "w", stderr);
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

    int t=1;
    // cin >> t;
    while(t--){
        solve();
    }

    #ifdef ONPC
    cerr<<'\n'<<"Time taken : "<<((double)(clock()-tStart)/CLOCKS_PER_SEC)*1000<<" ms"<<'\n';    
    #endif
    
    return 0;
}

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