oj.uz

Submission #1037028

# Submission time Handle Problem Language Result Execution time Memory
1037028 2024-07-27T22:32:43 Z ArthuroWich Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 458 ms 212700 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve() {
    int n, m, ans = 0;
    cin >> n >> m;
    vector<string> grid(n);
    vector<vector<int>> dist(n, vector<int>(m, 0)); 
    for (string &x : grid) {
        cin >> x;
    }
    deque<pair<int, int>> q;
    dist[0][0] = 1;
    q.push_back({0, 0});
    while(!q.empty()) {
        auto [i, j] = q.front();
        q.pop_front();
        if (i+1 < n && !dist[i+1][j] && grid[i+1][j] != '.') {
            dist[i+1][j] = dist[i][j];
            if (grid[i][j] != grid[i+1][j]) {
                dist[i+1][j]++;
                q.push_back({i+1, j});
            } else {
                q.push_front({i+1, j});
            }
        }
        if (j+1 < m && !dist[i][j+1] && grid[i][j+1] != '.') {
            dist[i][j+1] = dist[i][j];
            if (grid[i][j] != grid[i][j+1]) {
                dist[i][j+1]++;
                q.push_back({i, j+1});
            } else {
                q.push_front({i, j+1});
            }
        }
        if (i-1 >= 0 && !dist[i-1][j] && grid[i-1][j] != '.') {
            dist[i-1][j] = dist[i][j];
            if (grid[i][j] != grid[i-1][j]) {
                dist[i-1][j]++;
                q.push_back({i-1, j});
            } else {
                q.push_front({i-1, j});
            }
        }
        if (j-1 >= 0 && !dist[i][j-1] && grid[i][j-1] != '.') {
            dist[i][j-1] = dist[i][j];
            if (grid[i][j] != grid[i][j-1]) {
                dist[i][j-1]++;
                q.push_back({i, j-1});
            } else {
                q.push_front({i, j-1});
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans << endl;
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    t = 1;
    while(t--) {
        solve();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2648 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 2140 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 2 ms 1316 KB Output is correct
13 Correct 1 ms 1116 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 6 ms 2544 KB Output is correct
16 Correct 6 ms 2652 KB Output is correct
17 Correct 5 ms 2396 KB Output is correct
18 Correct 4 ms 2140 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 27 ms 14364 KB Output is correct
3 Correct 157 ms 143636 KB Output is correct
4 Correct 53 ms 33628 KB Output is correct
5 Correct 109 ms 80628 KB Output is correct
6 Correct 438 ms 171432 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 27 ms 14428 KB Output is correct
14 Correct 15 ms 8540 KB Output is correct
15 Correct 10 ms 9308 KB Output is correct
16 Correct 13 ms 6208 KB Output is correct
17 Correct 81 ms 36632 KB Output is correct
18 Correct 43 ms 35932 KB Output is correct
19 Correct 49 ms 33628 KB Output is correct
20 Correct 37 ms 31068 KB Output is correct
21 Correct 99 ms 83536 KB Output is correct
22 Correct 112 ms 80724 KB Output is correct
23 Correct 150 ms 69468 KB Output is correct
24 Correct 101 ms 81492 KB Output is correct
25 Correct 207 ms 143508 KB Output is correct
26 Correct 270 ms 210188 KB Output is correct
27 Correct 370 ms 212700 KB Output is correct
28 Correct 458 ms 171456 KB Output is correct
29 Correct 450 ms 166732 KB Output is correct
30 Correct 402 ms 178872 KB Output is correct
31 Correct 301 ms 92828 KB Output is correct
32 Correct 336 ms 192080 KB Output is correct