# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
783134 |
2023-07-14T15:52:26 Z |
serifefedartar |
Zoo (COCI19_zoo) |
C++17 |
|
267 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;
vector<vector<char>> grid;
int ans = 1, now = 1;
int 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));
cin >> R >> C;
grid = vector<vector<char>>(R+1, vector<char>(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++)
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<set<int>>(now, set<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].insert(to);
tree[to].insert(from);
}
}
}
}
dfs2(1, -1, 1);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
267 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
267 ms |
524288 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |