oj.uz

Submission #798440

# Submission time Handle Problem Language Result Execution time Memory
798440 2023-07-30T17:32:08 Z arijit_biswas Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 669 ms 119516 KB 
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;

// void setIO(string filename) {
//     freopen((filename + ".in").c_str(), "r", stdin);
//     freopen((filename + ".out").c_str(), "w", stdout);
// }

int n, m;
vector<vector<char>> snow;
vector<vector<int>> dis;
int ans;

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

bool check(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != '.');
}

void bfs() {
    dis.assign(n, vector<int>(m, 1e9));
    deque<pair<int, int>> dq;
    dis[0][0] = 0;
    dq.push_back({0, 0});
    while (!dq.empty()) {
        auto node = dq.front(); dq.pop_front();
        int i = node.first, j = node.second;
        ans = max(ans, dis[i][j]);
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (check(x, y)) {
                int c = (snow[x][y] == snow[i][j]) ? 0 : 1;
                if (dis[x][y] > dis[i][j] + c) {
                    dis[x][y] = dis[i][j] + c;
                    if (c == 0) {
                        dq.push_front({x, y});
                    } else {
                        dq.push_back({x, y});
                    }
                }
            }
        }
    }
}

void solution() {
    cin >> n >> m;
    snow.resize(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> snow[i][j];
        }
    }
    bfs();
    cout << ans + 1 << endl;
}

int main() {
    // setIO("");
    fast;
    solution();
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1748 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 6 ms 1472 KB Output is correct
5 Correct 2 ms 712 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 3 ms 724 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 9 ms 1748 KB Output is correct
16 Correct 11 ms 1748 KB Output is correct
17 Correct 7 ms 1748 KB Output is correct
18 Correct 6 ms 1364 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 39 ms 9576 KB Output is correct
3 Correct 277 ms 87876 KB Output is correct
4 Correct 72 ms 22448 KB Output is correct
5 Correct 181 ms 53348 KB Output is correct
6 Correct 653 ms 102252 KB Output is correct
7 Correct 2 ms 852 KB Output is correct
8 Correct 2 ms 840 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 39 ms 9556 KB Output is correct
14 Correct 23 ms 5572 KB Output is correct
15 Correct 18 ms 6228 KB Output is correct
16 Correct 19 ms 4052 KB Output is correct
17 Correct 106 ms 24284 KB Output is correct
18 Correct 81 ms 23864 KB Output is correct
19 Correct 75 ms 22428 KB Output is correct
20 Correct 61 ms 20616 KB Output is correct
21 Correct 164 ms 55004 KB Output is correct
22 Correct 179 ms 53360 KB Output is correct
23 Correct 221 ms 45988 KB Output is correct
24 Correct 157 ms 53836 KB Output is correct
25 Correct 458 ms 87744 KB Output is correct
26 Correct 669 ms 119516 KB Output is correct
27 Correct 595 ms 113364 KB Output is correct
28 Correct 651 ms 102040 KB Output is correct
29 Correct 653 ms 99400 KB Output is correct
30 Correct 654 ms 104872 KB Output is correct
31 Correct 454 ms 60136 KB Output is correct
32 Correct 618 ms 111744 KB Output is correct