oj.uz

Submission #700980

# Submission time Handle Problem Language Result Execution time Memory
700980 2023-02-19T15:30:17 Z phi Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1060 ms 112196 KB 
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#include <deque>
#include <cmath>

using namespace std;

vector<int> dx = { 1, -1, 0, 0 };
vector<int> dy = { 0, 0, 1, -1 };

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> snow(h);
    for (int i = 0; i < h; i++) cin >> snow[i];

    vector<vector<int>> depth(h, vector<int>(w));

    auto inside = [&](int y, int x) {
        return 0 <= x && x < w && 0 <= y && y < h && snow[y][x] != '.';
    };

    int ans = 1;

    deque<pair<int, int>> visit;
    visit.push_back({ 0, 0 });
    depth[0][0] = 1;

    while (!visit.empty()) {
        auto [ x, y ] = visit.front();
        visit.pop_front();

        ans = max(ans, depth[y][x]);

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inside(ny, nx) && depth[ny][nx] == 0) {
                if (snow[y][x] == snow[ny][nx]) {
                    depth[ny][nx] = depth[y][x];
                    visit.push_front({ nx, ny });
                } else {
                    depth[ny][nx] = depth[y][x] + 1;
                    visit.push_back({ nx, ny });
                }
            }
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2004 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 9 ms 1492 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 568 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 4 ms 852 KB Output is correct
15 Correct 13 ms 1984 KB Output is correct
16 Correct 19 ms 2036 KB Output is correct
17 Correct 13 ms 1916 KB Output is correct
18 Correct 8 ms 1464 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 59 ms 9036 KB Output is correct
3 Correct 460 ms 93820 KB Output is correct
4 Correct 118 ms 22408 KB Output is correct
5 Correct 275 ms 47428 KB Output is correct
6 Correct 878 ms 107024 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 488 KB Output is correct
11 Correct 3 ms 808 KB Output is correct
12 Correct 1 ms 440 KB Output is correct
13 Correct 61 ms 9056 KB Output is correct
14 Correct 36 ms 5856 KB Output is correct
15 Correct 37 ms 6460 KB Output is correct
16 Correct 29 ms 3796 KB Output is correct
17 Correct 169 ms 24160 KB Output is correct
18 Correct 145 ms 23892 KB Output is correct
19 Correct 121 ms 22428 KB Output is correct
20 Correct 118 ms 20672 KB Output is correct
21 Correct 303 ms 49044 KB Output is correct
22 Correct 314 ms 47424 KB Output is correct
23 Correct 307 ms 40400 KB Output is correct
24 Correct 268 ms 48188 KB Output is correct
25 Correct 615 ms 93804 KB Output is correct
26 Correct 835 ms 112196 KB Output is correct
27 Correct 828 ms 111760 KB Output is correct
28 Correct 874 ms 106792 KB Output is correct
29 Correct 914 ms 104372 KB Output is correct
30 Correct 1060 ms 108812 KB Output is correct
31 Correct 572 ms 53112 KB Output is correct
32 Correct 780 ms 110176 KB Output is correct