Submission #1203755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203755		arman42	Tracks in the Snow (BOI13_tracks)	C++20	31.77 / 100	507 ms	223852 KiB

tracks

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

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << ")", dbg_out(__VA_ARGS__)

#define endl '\n'
#define int long long

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX >> 1;

string a[4000];
int depth[4000][4000];

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;

    function<void(int, int)> bfs = [&] (int sx, int sy) {
        deque<pair<int, int>> q;
        q.push_back({sx, sy});
        depth[sx][sy] = 1;

        while (!q.empty()) {
            auto &[x, y] = q.front(); q.pop_front();
            ans = max(ans, depth[x][y]);

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < m && a[nx][ny] != '.' && depth[nx][ny] == 0) {
                    if (a[x][y] == a[nx][ny]) {
                        depth[nx][ny] = depth[x][y];
                        q.push_front({nx, ny});
                    } else {
                        depth[nx][ny] = depth[x][y] + 1;
                        q.push_back({nx, ny});
                    }
                }
            }
        }
    };

    bfs(0, 0);
    cout << ans << '\n';
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int tc = 1;
    // cin >> tc;

    while (tc--)  solve();
}

• Subtask 1: 3.3333 / 30
• Subtask 2: 28.4375 / 70