oj.uz

Submission #783290

# Submission time Handle Problem Language Result Execution time Memory
783290 2023-07-14T19:47:45 Z serifefedartar Zoo (COCI19_zoo) C++17
0 / 110
 4 ms 5716 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 1000005

int R, C, no = 1, ans = 1;
vector<vector<int>> mark(1005, vector<int>(1005, -1));
vector<vector<int>> graph;
vector<int> delRow = {-1, 0, 0, 1};
vector<int> delCol = {0, -1, 1, 0};
vector<vector<char>> grid;
bool vis[1005][1005];

bool check(int row, int col) {
    if (row <= 0 || row > R || col <= 0 || col > C)
        return false;
    return true;
}

void addEdge(int from, int to) {
    for (auto u : graph[from])
        if (u == to)
            return ;
    graph[from].push_back(to);
    graph[to].push_back(from);
}

void dfs(int i, int j) {
    vis[i][j] = true;
    mark[i][j] = no;
    for (int q = 0; q < 4; q++) {
        int nRow = i + delRow[q];
        int nCol = j + delCol[q];
        if (check(nRow, nCol) && grid[nRow][nCol] == grid[i][j] && !vis[nRow][nCol])
            dfs(nRow, nCol);
    }
}

void dfs2(int i, int j) {
    vis[i][j] = true;
    for (int q = 0; q < 4; q++) {
        int nRow = i + delRow[q];
        int nCol = j + delCol[q];
        if (!check(nRow, nCol) || grid[nRow][nCol] == '*' || vis[nRow][nCol])
            continue;

        int from = mark[i][j];
        int to = mark[nRow][nCol];
        if (from != to && from != -1 && to != -1)
            addEdge(from, to);

        if (grid[nRow][nCol] != '*')
            dfs2(nRow, nCol);
    }
}

void bfs(int node) {
    vector<int> vis(no+1, false);
    queue<pair<int,int>> q;
    q.push({node, 1});
    while (!q.empty()) {
        int node = q.front().first;
        int dist = q.front().second;
        q.pop();
        ans = max(ans, dist);

        if (vis[node])
            continue;
        vis[node] = true;

        for (auto u : graph[node]) {
            if (!vis[u])
                q.push({u, dist+1});
        }
    }
}

int main() {
    fast
    memset(vis, false, sizeof(vis));
    string s;
    cin >> R >> C;

    grid = vector<vector<char>>(R+1, vector<char>(C+1));
    for (int i = 1; i <= R; i++) {
        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] != '*') {
                dfs(i, j);
                no++;
            }
        }
    }
    graph = vector<vector<int>>(no+1, vector<int>(0));
    memset(vis, false, sizeof(vis));
    dfs2(1, 1);
    bfs(1);
    cout << ans << endl;
}

Subtask #1
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5700 KB Output is correct
8 Correct 4 ms 5588 KB Output is correct
9 Incorrect 3 ms 5588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 3 ms 5588 KB Output is correct
6 Correct 3 ms 5716 KB Output is correct
7 Correct 4 ms 5700 KB Output is correct
8 Correct 4 ms 5588 KB Output is correct
9 Incorrect 3 ms 5588 KB Output isn't correct
10 Halted 0 ms 0 KB -