Submission #148261

#	Time	Username	Problem	Language	Result	Execution time	Memory
148261		dolphingarlic	Tracks in the Snow (BOI13_tracks)	C++14	0 / 100	2128 ms	1048580 KiB

tracks

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, component[4000][4000], ans = 1;
char snow[4000][4000];

int num = 1;
vector<int> graph[16000050];
int visited[16000050];

void floodfill(int c, int x, int y) {
    component[x][y] = c;

    if (x > 0 && snow[x - 1][y] != '.') {
        if (snow[x - 1][y] == snow[x][y] && !component[x - 1][y]) floodfill(c, x - 1, y);
        else if (component[x - 1][y]) {
            graph[c].push_back(component[x - 1][y]);
            // graph[component[x - 1][y]].push_back(c);
        }
    }
    if (x < n - 1 && snow[x + 1][y] != '.') {
        if (snow[x + 1][y] == snow[x][y] && !component[x + 1][y]) floodfill(c, x + 1, y);
        else if (component[x + 1][y]) {
            graph[c].push_back(component[x + 1][y]);
            // graph[component[x + 1][y]].push_back(c);
        }
    }
    if (y > 0 && snow[x][y - 1] != '.') {
        if (snow[x][y - 1] == snow[x][y] && !component[x][y - 1]) floodfill(c, x, y - 1);
        else if (component[x][y - 1]) {
            graph[c].push_back(component[x][y - 1]);
            // graph[component[x][y - 1]].push_back(c);
        }
    }
    if (y < m - 1 && snow[x][y + 1] != '.') {
        if (snow[x][y + 1] == snow[x][y] && !component[x][y + 1]) floodfill(c, x, y + 1);
        else if (component[x][y + 1]) {
            graph[c].push_back(component[x][y+ 1]);
            // graph[component[x][y + 1]].push_back(c);
        }
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    FOR(i, 0, n) FOR(j, 0, m) cin >> snow[i][j];

    FOR(i, 0, n) FOR(j, 0, m) {
        if (!component[i][j] && snow[i][j] != '.') {
            floodfill(num++, i, j);
        }
    }

    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int i : graph[curr]) {
            if (!visited[i]) {
                visited[i] = visited[curr] + 1;
                ans = max(ans, visited[i]);
                q.push(i);
            }
        }
    }

    cout << ans;
    return 0;
}

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