Submission #537649

#	Time	Username	Problem	Language	Result	Execution time	Memory
537649		Servus2022	Zoo (COCI19_zoo)	C++14	110 / 110	160 ms	37496 KiB

zoo

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1005;

int N, M;
char ch[NMAX][NMAX];

bool Interior (pair<int,int>  x) {
    return 0 < x.first && x.first <= N && 0 < x.second && x.second <= M;
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j )
            cin >> ch[i][j];
}

int viz[NMAX][NMAX];
int vf = 0;
vector <int> G[NMAX*NMAX];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void Lee (int L, int C, char car) {
    ++ vf;
    viz[L][C] = vf;
    queue <pair<int,int> > Q;
    set <int> S;
    Q.push({L, C});

    while (!Q.empty()) {
        pair<int,int>  x = Q.front();
        Q.pop();

        for (int i = 0; i < 4; ++ i ) {
            pair<int,int>  vecin = make_pair(x.first + dx[i], x.second + dy[i]);

            if (!Interior(vecin) || ch[vecin.first][vecin.second] == '*' || viz[vecin.first][vecin.second] == vf) continue;
            if (viz[vecin.first][vecin.second] != 0) {
                S.insert(viz[vecin.first][vecin.second]);
                continue;
            }

            if (ch[vecin.first][vecin.second] == car) {
                Q.push(vecin);
                viz[vecin.first][vecin.second] = vf;
            }
        }
    }

    while (!S.empty()) {
        int it = *S.begin();
        S.erase(S.begin());
        G[it].push_back(vf);
        G[vf].push_back(it);
    }
}

bool sel[NMAX*NMAX];

void Bfs (int Node) {
    queue <pair<int,int> > Q;
    Q.push({Node, 1});
    for (int i = 1; i <= vf; ++ i )
        sel[i] = 0;
    sel[Node] = 1;
    int Max = 0;

    while (!Q.empty()) {
        int x = Q.front().first;
        int lung = Q.front().second;
        Max = max(Max, lung);

        Q.pop();

        for (int i = 0; i < G[x].size(); ++ i ) {
            int it = G[x][i];
            if (sel[it]) continue;

            Q.push({it, lung+1});
            sel[it] = 1;
        }
    }

    cout << Max << '\n';
}

void Solve () {
    for (int i = 1; i <= N; ++ i ) {
        for (int j = 1; j <= M; ++ j ) {
            if (ch[i][j] == '*') continue;

            if (viz[i][j] != 0) continue;

            Lee(i, j, ch[i][j]);
        }
    }

    Bfs(1);
}

int main () {
    Read();

    Solve();

    return 0;
}

Compilation message (stderr)

zoo.cpp: In function 'void Bfs(int)':
zoo.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 0; i < G[x].size(); ++ i ) {
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 45 / 45
• Subtask 2: 65 / 65