Submission #575627

#TimeUsernameProblemLanguageResultExecution timeMemory
575627ktkeremTracks in the Snow (BOI13_tracks)C++17
100 / 100
1130 ms202268 KiB
/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
/*#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 vll;
typedef unsigned __int128 uvll;
ll _i=0;
#define ffn(x) _i=x
#define llll std::pair<ll , ll>
#define stitr set<ll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e9 + 7; 
const ll ous = 1e6 + 7;
const ll dx[4] = {1 , 0 , 0 , -1} , dy[4] = {0,1,-1,0};
void solve(){
    ll n , m;std::cin >> n >> m;
    ll vis[n+5][m+5];
    memset(vis , 0 , sizeof(vis));
    std::string h[n];
    fora(i , n){
        std::cin >> h[i];
    }
    std::vector<llll> v; 
    v.pb({0 , 0});
    std::queue<llll> que;
    ll ans = 0;
    while(!v.empty()){
        for(auto j:v){
            que.push(j);
        }
        v.clear();
        while(!que.empty()){
            llll a = que.front();
            que.pop();
            if(vis[a.fi][a.sec] == 2){
                continue;
            }
            vis[a.fi][a.sec] = 2;
            fora(i , 4){
                if(dx[i] + a.fi >= 0 && dx[i] + a.fi < n && dy[i] + a.sec >= 0 && dy[i] + a.sec < m && h[dx[i] + a.fi][dy[i] + a.sec] != '.'){
                    if(h[dx[i] + a.fi][dy[i] + a.sec] == h[a.fi][a.sec] && vis[dx[i] + a.fi][dy[i] + a.sec] == 0){
                        vis[dx[i] + a.fi][dy[i] + a.sec] = 1;
                        que.push({dx[i] + a.fi , dy[i] + a.sec});
                    }
                    else if(vis[dx[i] + a.fi][dy[i] + a.sec] == 0){
                        vis[dx[i] + a.fi][dy[i] + a.sec] = 1;
                        v.pb({dx[i] + a.fi , dy[i] + a.sec});
                    }
                }
            }
        }
        ans++;
    }
    std::cout << ans << "\n";
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0; 
}

Compilation message (stderr)

tracks.cpp:12:1: warning: "/*" within comment [-Wcomment]
   12 | /**/
      |  
tracks.cpp: In function 'int main()':
tracks.cpp:78:8: warning: unused variable 'o' [-Wunused-variable]
   78 |     ll o = 1;
      |        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...