oj.uz

Submission #374229

# Submission time Handle Problem Language Result Execution time Memory
374229 2021-03-06T23:47:14 Z daduam Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1582 ms 111208 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> meadow(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> meadow[i][j];
        }
    }

    vector<vector<int>> d(n, vector<int>(m));
    deque<pair<int, int>> q;
    q.push_front({0, 0});
    d[0][0] = 1;

    int rv = 0;
    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop_front();
        rv = max(rv, d[r][c]);
        static vector<pair<int, int>> dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (auto [x, y] : dirs) {
            x += r, y += c;
            if (x >= 0 && x < n && y >= 0 && y < m && !d[x][y] &&
                meadow[x][y] != '.') {
                if (meadow[r][c] != meadow[x][y]) {
                    d[x][y] = d[r][c] + 1;
                    q.push_back({x, y});
                } else {
                    d[x][y] = d[r][c];
                    q.push_front({x, y});
                }
            }
        }
    }

    cout << rv << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1772 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 15 ms 1516 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 6 ms 748 KB Output is correct
11 Correct 4 ms 620 KB Output is correct
12 Correct 9 ms 876 KB Output is correct
13 Correct 7 ms 876 KB Output is correct
14 Correct 7 ms 876 KB Output is correct
15 Correct 23 ms 2028 KB Output is correct
16 Correct 24 ms 1772 KB Output is correct
17 Correct 21 ms 1772 KB Output is correct
18 Correct 15 ms 1516 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 127 ms 8968 KB Output is correct
3 Correct 1107 ms 79596 KB Output is correct
4 Correct 274 ms 19564 KB Output is correct
5 Correct 639 ms 45292 KB Output is correct
6 Correct 1538 ms 94284 KB Output is correct
7 Correct 4 ms 876 KB Output is correct
8 Correct 5 ms 876 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 4 ms 876 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 127 ms 8812 KB Output is correct
14 Correct 85 ms 5612 KB Output is correct
15 Correct 74 ms 5996 KB Output is correct
16 Correct 55 ms 4076 KB Output is correct
17 Correct 334 ms 21100 KB Output is correct
18 Correct 297 ms 20844 KB Output is correct
19 Correct 272 ms 19564 KB Output is correct
20 Correct 240 ms 18028 KB Output is correct
21 Correct 652 ms 46772 KB Output is correct
22 Correct 643 ms 45244 KB Output is correct
23 Correct 651 ms 39280 KB Output is correct
24 Correct 640 ms 45600 KB Output is correct
25 Correct 1304 ms 79468 KB Output is correct
26 Correct 1070 ms 111208 KB Output is correct
27 Correct 1440 ms 108704 KB Output is correct
28 Correct 1582 ms 94032 KB Output is correct
29 Correct 1523 ms 90136 KB Output is correct
30 Correct 1467 ms 97404 KB Output is correct
31 Correct 1105 ms 51180 KB Output is correct
32 Correct 1388 ms 98728 KB Output is correct