Submission #928400

#	Time	Username	Problem	Language	Result	Execution time	Memory
928400		Whisper	Zoo (COCI19_zoo)	C++17	110 / 110	40 ms	3420 KiB

zoo

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

#define ii pair< int , int >
#define pb push_back
#define fi first
#define se second

#define all(x) begin(x) , end(x)
#define full(x) x + 1 , x + n + 1

#define MASK(i) 1LL << i 
#define bit(x, i) ( (x) & MASK(i) )
#define popcount(i) __builtin_popcountll(i)
#define set_on(x, i) ( (x) | MASK(i) )
#define set_off( x, i ) ( (x) & ~MASK(i) )
 
using namespace std; 
using ll = long long;
using str = string;

constexpr ll P[4] = {'U', 'L', 'R', 'D'};
constexpr ll dx[8] = {-1, -1, 1, 1, 0, 0, -1, 1};
constexpr ll dy[8] = {-1, 1, -1, 1, -1, 1, 0, 0};

constexpr ll L = 1e3 + 5;
constexpr ll LINF = ( 1e18 + 5 );
constexpr ll N = 1e6 + 5;
constexpr ll inf = ( 1e9 + 5 );
constexpr int MOD = 1e9 + 7;

template<class X  , class Y>
    bool maximize( X& x , const Y& y ){
        if ( x < y ){
            x = y;
            return true;
        }
        return false;
    }
template<class X , class Y>
    bool minimize( X& x , const Y& y ){
        if ( x > y ){
            x = y;
            return true;
        }
        return false;
    }
template<class T> using MaxHeap = priority_queue< T , vector<T> , less<T> >;
template<class T> using MinHeap = priority_queue< T , vector<T> , greater<T> >;

queue<ii> meet, Q;
bool vst[L][L];
ll res = 0;
char a[L][L];
ll n, m;
bool isOk( ll x , ll y ){
    return x >= 1 && x <= n  && y >= 1 && y <= m && !vst[x][y] && a[x][y] != '*';
}
void bfs(){
    res++;
    auto [ X , Y ] = Q.front();
    while ( !Q.empty() ){
       auto[ x, y ] = Q.front(); Q.pop();
        for ( int i = 4 ; i < 8 ; i++ ){
            ll nx = dx[i] + x;
            ll ny = dy[i] + y;
            if ( isOk( nx, ny ) ){
                if ( a[nx][ny] == a[X][Y] ) Q.emplace( nx , ny );
                else meet.emplace( nx , ny );
                vst[nx][ny] = true;
            }
        }
    }
    swap( meet, Q );
}
void Whisper(){
    cin >> n >> m;
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 1 ; j <= m ; j++ ){
            cin >> a[i][j];
        }
    }
    vst[1][1] = true;
    Q.emplace( 1, 1 );
    while ( !Q.empty() )
            bfs();
    cout << res;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    #define TASK "__Whisper"
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ll Test = 1; //cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){

        Whisper();
        //
        cout << '\n';
    }
}

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65