Submission #474815

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

tracks

#include <bits/stdc++.h>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<char>> g(n, std::vector<char>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> g[i][j];
        }
    }
    std::vector<std::vector<int>> comp(n, std::vector<int>(m, -1));
    std::vector<std::vector<bool>> connect(n, std::vector<bool>(m, false));
    int num = 0;
    std::function<void(int, int, char)> dfs=[&](int x, int y, char c) {
        if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '.')
            return;
        if (comp[x][y] != -1 && comp[x][y] != num) {
            connect[num][comp[x][y]] = true;
            connect[comp[x][y]][num] =  true;
        }
        if (comp[x][y] != -1 || g[x][y] != c)
            return;
        comp[x][y] = num;
        dfs(x + 1, y, c);
        dfs(x - 1, y, c);
        dfs(x, y + 1, c);
        dfs(x, y - 1, c);
    };
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < m; ++y) {
            if (comp[x][y] != -1 || g[x][y] == '.')
                continue;
            dfs(x, y, g[x][y]);
            num++;
        }
    }
    std::vector<std::vector<int>> adj(n + m);
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < m; ++j) {
            if (connect[i][j]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    std::vector<int> d(num, 0);
    std::queue<int> q;
    q.push(0);
    d[0] = 1;
    int ans = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d[v] == 0) {
                q.push(v);
                d[v] = d[u] + 1;
                ans = std::max(ans, d[v]);
            }
        }
    }
    std::cout << ans << "\n";
    return 0;
}

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