Submission #385834

#	Time	Username	Problem	Language	Result	Execution time	Memory
385834		dolphingarlic	Tracks in the Snow (BOI13_tracks)	C++14	80.31 / 100	2142 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;
unordered_set<int> graph[8000050];
int visited[8000050], q[8000050];
 
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].insert(component[x - 1][y]);
            graph[component[x - 1][y]].insert(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].insert(component[x + 1][y]);
            graph[component[x + 1][y]].insert(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].insert(component[x][y - 1]);
            graph[component[x][y - 1]].insert(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].insert(component[x][y+ 1]);
            graph[component[x][y + 1]].insert(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);
        }
    }
 
    int rp = -1, lp = 0;
    q[++rp] = 1;
    visited[1] = 1;
    while (rp >= lp) {
        int curr = q[lp++];
 
        for (int i : graph[curr]) {
            if (!visited[i]) {
                visited[i] = visited[curr] + 1;
                ans = max(ans, visited[i]);
                q[++rp] = i;
            }
        }
    }
 
    cout << ans;
    return 0;
}

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