oj.uz

Submission #783106

# Submission time Handle Problem Language Result Execution time Memory
783106 2023-07-14T15:31:04 Z serifefedartar Zoo (COCI19_zoo) C++17
0 / 110
 367 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MAXN 100005

vector<set<int>> tree;
vector<vector<int>> mark, grid;
int ans = 1, now = 1;
int R, C;
int vis[1005][1005];
void dfs2(int node, int parent, int dist) {
    ans = max(ans, dist);
    for (auto u : tree[node]) {
        if (u == parent)
            continue;
        dfs2(u, node, dist + 1);
    }
}

void dfs(int i, int j) {
    vis[i][j] = true;
    mark[i][j] = now;
    vector<int> delRow = {-1, 0, 0, 1};
    vector<int> delCol = {0, -1, 1, 0};
    for (int q = 0; q < 4; q++) {
        int nRow = delRow[q] + i;
        int nCol = delCol[q] + j;
        if (nRow <= 0 || nRow > R || nCol <= 0 || nCol > C 
            || vis[nRow][nCol] || grid[nRow][nCol] != grid[i][j])
            continue;
        dfs(nRow, nCol);
    }
}

int main() {
    fast
    memset(vis, 0, sizeof(vis));
    cin >> R >> C;

    grid = vector<vector<int>>(R+1, vector<int>(C+1));
    mark = vector<vector<int>>(R+1, vector<int>(C+1,-1));
    for (int i = 1; i <= R; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= C; j++) {
            if (s[j-1] == '*')
                grid[i][j] = 0;
            else if (s[j-1] == 'B')
                grid[i][j] = 1;
            else
                grid[i][j] = 2;
        }
    }
    
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (vis[i][j] || grid[i][j] == 0 )
                continue;
            dfs(i, j);
            now++;
        }
    }

    tree = vector<set<int>>(now, set<int>());
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            vector<int> delRow = {-1, 0, 0, 1};
            vector<int> delCol = {0, -1, 1, 0};
            for (int q = 0; q < 4; q++) {
                int nRow = delRow[q] + i;
                int nCol = delCol[q] + j;
                if (nRow <= 0 || nRow > R || nCol <= 0 || nCol > C 
                    || mark[nRow][nCol] == mark[i][j])
                    continue;
                int from = mark[nRow][nCol];
                int to = mark[i][j];
                if (from == -1 || to == -1)
                    continue;
                tree[from].insert(to);
                tree[to].insert(from);
            }
        }
    }
    dfs2(1, -1, 1);
    cout << ans << endl;
}

Subtask #1
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 367 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Runtime error 367 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -