Submission #704783

#	Time	Username	Problem	Language	Result	Execution time	Memory
704783		becaido	Zoo (COCI19_zoo)	C++17	110 / 110	38 ms	3308 KiB

zoo

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};
const int SIZE = 1005;

int n, m, cnt;
string s[SIZE];
bool vs[SIZE][SIZE];
queue<pair<int, int>> q[2];

int type(char c) {
    return c == 'B' ? 0 : c == 'T' ? 1 : 2;
}

void solve() {
    cin >> n >> m;
    FOR (i, 1, n) cin >> s[i], s[i] = " " + s[i];

    char c = s[1][1];
    q[type(s[1][1])].emplace(1, 1);
    vs[1][1] = 1;

    while (q[0].size() || q[1].size()) {
        int t = type(c);
        while (q[t].size()) {
            auto [x, y] = q[t].front();
            q[t].pop();
            FOR (i, 0, 3) {
                int tx = x + dx[i], ty = y + dy[i];
                if (1 <= tx && tx <= n && 1 <= ty && ty <= m && !vs[tx][ty] && type(s[tx][ty]) <= 1) {
                    vs[tx][ty] = 1;
                    q[type(s[tx][ty])].emplace(tx, ty);
                }
            }
        }
        cnt++;
        c = c == 'B' ? 'T' : 'B';
    }
    cout << cnt << '\n';
}

int main() {
    Waimai;
    solve();
}

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