Submission #511191

#	Time	Username	Problem	Language	Result	Execution time	Memory
511191		DragosC1	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	1268 ms	1048580 KiB

tracks

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
vector<vector<int>> a;
char mat[4001][4001];
int comp[4001][4001];
bool viz[16000001];
queue<pair<int, int>> Q;
 
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
int n, m;
int l;
int Max;
 
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, 1, 0, -1}; 
 
bool inside(int i, int j) {
    if (i >= 1 && i <= n && j >= 1 && j <= m)
        return 1;
    return 0;
}
 
void dfs1(int i, int j) {
    int k, inou, jnou;
    comp[i][j] = l;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        if (inside(inou, jnou) && !comp[inou][jnou] && mat[inou][jnou] == mat[i][j])
            dfs1(inou, jnou);
    }
}
 
void dfs2(int i, int j) {
    int k, inou, jnou;
    viz[(i - 1) * m + j] = 1;
    for (k = 0; k < 4; k++) {
        inou = i + di[k], jnou = j + dj[k];
        if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] == mat[i][j])
            dfs2(inou, jnou);
        else if (inside(inou, jnou) && !viz[(inou - 1) * m + jnou] && mat[inou][jnou] != '.' && a[comp[i][j]].back() != comp[inou][jnou]) {
            a[comp[i][j]].emplace_back(comp[inou][jnou]);
            a[comp[inou][jnou]].emplace_back(comp[i][j]);
        }
    }
}
 
void bfs(int x) {
    int i;
    pair<int, int> p;
    Q.push({x, 1});
    viz[x] = 1;
    while (!Q.empty()) {
        p = Q.front();
        Q.pop();
        if (p.second > Max)
            Max = p.second;
        for (int y : a[p.first]) {
            if (!viz[y]) {
                viz[y] = 1;
                Q.push({y, p.second + 1});
            }
        }   
    }
}
 
int main() {
    fast
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            cin >> mat[i][j];
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (!comp[i][j] && mat[i][j] != '.') {
                l++;
                dfs1(i, j);
            }
    a.resize(l + 1);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            if (!viz[(i - 1) * m + j] && mat[i][j] != '.') 
                dfs2(i, j);
    for (i = 1; i <= l; i++)
        viz[i] = 0;
    bfs(1);
    cout << Max;
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void bfs(int)':
tracks.cpp:52:9: warning: unused variable 'i' [-Wunused-variable]
   52 |     int i;
      |         ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70