oj.uz

Submission #1017098

# Submission time Handle Problem Language Result Execution time Memory
1017098 2024-07-08T20:43:51 Z chayi Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 419 ms 131312 KB 
#include <bits/stdc++.h>

using namespace std;

int depth[4001][4001], ans = 1;
string s[4001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    int dx[]{0, -1, 0, 1, 0};

    auto good = [&](int x, int y) { return x >= 0 && x < n && y >= 0 && y < m && s[x][y] != '.'; };

    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    depth[0][0] = 1;
    
    while (!dq.empty()) {
        auto [x, y] = dq.front();
        dq.pop_front();
        ans = max(ans, depth[x][y]);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dx[i + 1];

            if (good(nx, ny) && depth[nx][ny] == 0) {
                if (s[x][y] == s[nx][ny]) {
                    depth[nx][ny] = depth[x][y];
                    dq.push_front({nx, ny});
                } else {
                    depth[nx][ny] = depth[x][y] + 1;
                    dq.push_back({nx, ny});
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3928 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 6 ms 3676 KB Output is correct
5 Correct 2 ms 1992 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 4 ms 2140 KB Output is correct
13 Correct 2 ms 2140 KB Output is correct
14 Correct 2 ms 1968 KB Output is correct
15 Correct 7 ms 3676 KB Output is correct
16 Correct 7 ms 3932 KB Output is correct
17 Correct 5 ms 3676 KB Output is correct
18 Correct 4 ms 3676 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 24 ms 11892 KB Output is correct
3 Correct 128 ms 75380 KB Output is correct
4 Correct 45 ms 29616 KB Output is correct
5 Correct 102 ms 51408 KB Output is correct
6 Correct 398 ms 110808 KB Output is correct
7 Correct 11 ms 16728 KB Output is correct
8 Correct 9 ms 15964 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 6 ms 16460 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 24 ms 12024 KB Output is correct
14 Correct 15 ms 8048 KB Output is correct
15 Correct 11 ms 10332 KB Output is correct
16 Correct 11 ms 4956 KB Output is correct
17 Correct 64 ms 25340 KB Output is correct
18 Correct 44 ms 32220 KB Output is correct
19 Correct 41 ms 29528 KB Output is correct
20 Correct 38 ms 22612 KB Output is correct
21 Correct 78 ms 50732 KB Output is correct
22 Correct 100 ms 51380 KB Output is correct
23 Correct 123 ms 42320 KB Output is correct
24 Correct 81 ms 47540 KB Output is correct
25 Correct 222 ms 96368 KB Output is correct
26 Correct 296 ms 131312 KB Output is correct
27 Correct 326 ms 126112 KB Output is correct
28 Correct 419 ms 110812 KB Output is correct
29 Correct 403 ms 108464 KB Output is correct
30 Correct 366 ms 111148 KB Output is correct
31 Correct 292 ms 72104 KB Output is correct
32 Correct 289 ms 118308 KB Output is correct