Submission #757707

#	Time	Username	Problem	Language	Result	Execution time	Memory
757707		drdilyor	Tracks in the Snow (BOI13_tracks)	C++17	3.33 / 100	2103 ms	1048576 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<string> mat(n);
    for (string& s : mat) {
        cin >> s;
    }
    auto id = [m](int i, int j) { return i* m + j;};
    vector<vector<pair<int,int>>> adj(n * m);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (auto [di, dj] : {pair{0, -1}, {0, 1}, {-1, 0}, {1, 0}}) {
                int ni = i + di;
                int nj = j + dj;
                if (clamp(ni, 0,n-1) == ni && clamp(nj, 0, m-1) == nj) {
                    if (mat[ni][nj] == '.' || mat[i][j] == '.') continue;
                    int c = mat[i][j] != mat[ni][nj];
                    adj[id(i, j)].push_back({id(ni, nj), c});
                }
            }
        }
    }

    static constexpr int inf = 1e9;
    vector<int> dist(n*m, inf);
    vector<bool> vis(n*m, 0), vis2(n*m, 0);
    int res = 0;
    vector<int> stk;
    stk.reserve(200*1000*1000);
    auto dfs = [&](int i, int d) -> void {
        stk.clear();
        stk.push_back(i);
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis[i] = 1;
            dist[i] = d;
            for (auto [e, ec]: adj[i]) {
                if (vis[e]) continue;
                if (!ec)
                    stk.push_back(e);
            }
            res = max(res, dist[i]);
        }
    };
    auto dfs_min = [&](int i) -> int {
        stk.clear();
        stk.push_back(i);
        int res = inf;
        while (stk.size()) {
            int i = stk.back();
            stk.pop_back();
            vis2[i] = 1;
            for (auto [e, ec]: adj[i]) {
                if (ec) res = min(res, dist[e]);
                if (vis2[e]) continue;
                if (!ec)
                    stk.push_back(e);
            }
        }
        return res;
    };
    dfs(0, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[id(i, j)]) continue;
            if (mat[i][j] == '.') continue;
            int d = dfs_min(id(i, j))+1;
            dfs(id(i, j), d);
        }
    }
    cout << res << '\n';
    
    

    return 0;
}

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