Submission #783146

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
783146	2023-07-14T15:59:56 Z	serifefedartar	Zoo (COCI19_zoo)	C++17	0 / 110	2000 ms	46692 KB

zoo

#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<vector<int>> tree;
char mark[1005][1005], grid[1005][1005];
int ans = 1, now = 1, R, C;
bool 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;
    for (int delRow = -1; delRow <= 1; delRow++) {
        for (int delCol = -1; delCol <= 1; delCol++) {
            if ((delCol == 0 && delRow == 0) || (delCol != 0 && delRow != 0))
                continue;
            int nRow = delRow + i;
            int nCol = delCol + 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));
    memset(mark, -1, sizeof(mark));
    cin >> R >> C;

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

    tree = vector<vector<int>>(now, vector<int>());
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            for (int delRow = -1; delRow <= 1; delRow++) {
                for (int delCol = -1; delCol <= 1; delCol++) {
                    if ((delCol == 0 && delRow == 0) || (delCol != 0 && delRow != 0))
                        continue;
                    int nRow = delRow + i;
                    int nCol = delCol + 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].push_back(to);
                    tree[to].push_back(from);
                }
            }
        }
    }
    dfs2(1, -1, 1);
    cout << ans << endl;
}

Subtask #1

0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2082 ms	46692 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2082 ms	46692 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-