oj.uz

Submission #307301

# Submission time Handle Problem Language Result Execution time Memory
307301 2020-09-27T15:12:52 Z tieunhi Zoo (COCI19_zoo) C++14
0 / 110
 18 ms 24320 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, m, root[N*N];
char c[N][N];
vector<int> g[N*N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int inline encode(int x, int y) {
    return (x - 1) * m + y;
}
int get_root(int u) {
    return (root[u] == 0) ? u : root[u] = get_root(root[u]);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
        }
    }

    // Merge same components
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '*') continue;
            for (int dir = 0; dir < 4; dir++) {
                int x = i + dx[dir];
                int y = j + dy[dir];
                if (x > n || x < 1 || y > m || y < 1) continue;
                if (c[x][y] != c[i][j]) continue;
                
                int p = get_root(encode(i, j));
                int q = get_root(encode(x, y));
                if (p != q) {
                    root[p] = q;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (c[i][j] == '*') continue;
            for (int dir = 0; dir < 4; dir++) {
                int x = i + dx[dir];
                int y = j + dy[dir];
                if (x > n || x < 1 || y > m || y < 1) continue;
                if (c[x][y] == c[i][j] || c[x][y] == '*') continue;
                
                int p = get_root(encode(i, j));
                int q = get_root(encode(x, y));
                g[p].push_back(q);
                g[q].push_back(p);
            }
        }
    }


    vector<int> d((n+1)*(m+1) + 1, 0);
    queue<int> q;
    int root = encode(n, m);
    q.push(root); d[root] = 1;
    int res = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        res = max(res, d[u]);
        for (auto v : g[u]) {
            if (d[v]) {
                continue;
            } else {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    cout <<res;
}

Subtask #1
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 17 ms 24064 KB Output is correct
3 Correct 17 ms 24064 KB Output is correct
4 Correct 17 ms 24192 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Incorrect 18 ms 24320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24064 KB Output is correct
2 Correct 17 ms 24064 KB Output is correct
3 Correct 17 ms 24064 KB Output is correct
4 Correct 17 ms 24192 KB Output is correct
5 Correct 18 ms 24320 KB Output is correct
6 Incorrect 18 ms 24320 KB Output isn't correct
7 Halted 0 ms 0 KB -