Submission #491743

#	Time	Username	Problem	Language	Result	Execution time	Memory
491743		hoanghq2004	Zoo (COCI19_zoo)	C++14	110 / 110	224 ms	49732 KiB

zoo

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int Nmax = 1010;

int n, m;
char c[Nmax][Nmax];
int par[Nmax * Nmax], sz[Nmax * Nmax], d[Nmax * Nmax];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector <int> g[Nmax * Nmax];

int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

void Union(int u, int v) {
    if ((u = Find(u)) == (v = Find(v))) return;
    if (sz[u] < sz[v]) swap(u, v);
    par[v] = u;
    sz[u] += sz[v];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> c[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) par[i * m + j] = i * m + j, sz[i * m + j] = 1;
    for (int u = 0; u < n; ++u)
        for (int v = 0; v < m; ++v) {
            if (c[u][v] == '*') continue;
            for (int i = 0; i < 4; ++i) {
                int x = u + dx[i], y = v + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || c[x][y] == '*') continue;
                if (c[x][y] == c[u][v]) Union(x * m + y, u * m + v);
            }
        }
    for (int u = 0; u < n; ++u)
        for (int v = 0; v < m; ++v) {
            if (c[u][v] == '*') continue;
            for (int i = 0; i < 4; ++i) {
                int x = u + dx[i], y = v + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || c[x][y] == '*') continue;
                if (c[x][y] != c[u][v]) {
                    g[Find(x * m + y)].push_back(Find(u * m + v));
                    g[Find(u * m + v)].push_back(Find(x * m + y));
                }
            }
        }
    queue <int> q;
    q.push(Find(0));
    for (int i = 0; i < n * m; ++i) d[i] = -1;
    d[Find(0)] = 1;
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (auto v: g[u]) {
            if (d[v] != -1) continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    cout << *max_element(d, d + n * m);
}

Compilation message (stderr)

zoo.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
zoo.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

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