Submission #675795

#	Time	Username	Problem	Language	Result	Execution time	Memory
675795		aaggupta07	Tracks in the Snow (BOI13_tracks)	C++17	97.81 / 100	1660 ms	1048576 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 4002
#define pb push_back

int n, m, curC = 1;
string grid[MAX_N];
int visited[MAX_N][MAX_N];
vector<set<int>> adj;
vector<int> distances;

void floodfill(int r, int c, char color) {
    if(r < 0 || r >= n || c < 0 || c >= m || grid[r][c] == '.') return;
    if(grid[r][c] != color && visited[r][c]) {
        adj[curC-1].insert(visited[r][c]-1);
        adj[visited[r][c]-1].insert(curC-1);
        return;
    }
    else if(visited[r][c] || grid[r][c] != color) return;

    visited[r][c] = curC;
    floodfill(r+1, c, color);
    floodfill(r-1, c, color);
    floodfill(r, c+1, color);
    floodfill(r, c-1, color);
}

void bfs(int node) {
    queue<int> q;
    q.push(node);
    distances[node] = 1;

    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for(int i: adj[cur]) {
            if(distances[i] == 0) {
                distances[i] = distances[cur] + 1;
                q.push(i);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; ++i) cin >> grid[i];

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(visited[i][j] == 0 && grid[i][j] != '.') {
                adj.pb(set<int>());
                floodfill(i, j, grid[i][j]);
                ++curC;
            }
        }
    }

    //for(int i = 0; i < n; ++i) cout << grid[i] << endl;
    // for(int i = 0; i < n; ++i) {for(int j = 0; j < m; ++j) cout << visited[i][j] << ' '; cout << endl;}

    // for(int i = 0; i < curC-1; ++i) { for(int j: adj[i]) cout << j << ' '; cout << endl; }
    distances.resize(curC-1);
    fill(distances.begin(), distances.end(), 0);
    
    bfs(0);
    int maxDist = 1;
    for(int i = 0; i < distances.size(); ++i) {
        // cout << distances[i] << endl;
        maxDist = max(maxDist, distances[i]);
    }

    cout << fixed << maxDist << '\n';
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i = 0; i < distances.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~~~~~

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