oj.uz

Submission #771186

# Submission time Handle Problem Language Result Execution time Memory
771186 2023-07-02T14:39:48 Z VMaksimoski008 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 674 ms 139352 KB 
#include <bits/stdc++.h>
using namespace std;

void setIO(string name = "") {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
}

int dr[4] = {0, -1, 0, 1};
int dc[4] = {-1, 0, 1, 0};

int main() {
    setIO();

    int n, m;
    cin >> n >> m;
    char mat[n][m];
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++) cin >> mat[i][j];

    bool vis[n][m];
    int dist[n][m];
    memset(dist, 0, sizeof(dist));
    memset(vis, false, sizeof(vis));

    int ans = 1;
    deque<pair<int, int> > q;
    q.push_front({0, 0});
    vis[0][0] = true;
    dist[0][0] = 1;

    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop_front();

        ans = max(ans, dist[r][c]);

        for(int i=0; i<4; i++) {
            int newR = r + dr[i];
            int newC = c + dc[i];

            if(vis[newR][newC]) continue;
            if(newR < 0 || newR >= n) continue;
            if(newC < 0 || newC >= m) continue;
            if(mat[newR][newC] == '.') continue;

            if(mat[r][c] == mat[newR][newC]) {
                dist[newR][newC] = dist[r][c];
                vis[newR][newC] = true;
                q.push_front({ newR, newC });
            }

            if(mat[r][c] != mat[newR][newC]) {
                dist[newR][newC] = dist[r][c] + 1;
                vis[newR][newC] = true;
                q.push_back({ newR, newC });
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2004 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 6 ms 1476 KB Output is correct
5 Correct 3 ms 852 KB Output is correct
6 Correct 1 ms 212 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 2 ms 716 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 2 ms 848 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 10 ms 1996 KB Output is correct
16 Correct 11 ms 1940 KB Output is correct
17 Correct 9 ms 1868 KB Output is correct
18 Correct 5 ms 1492 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 40 ms 10924 KB Output is correct
3 Correct 297 ms 109872 KB Output is correct
4 Correct 73 ms 25984 KB Output is correct
5 Correct 162 ms 61824 KB Output is correct
6 Correct 673 ms 124472 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 1 ms 544 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 42 ms 10920 KB Output is correct
14 Correct 23 ms 6484 KB Output is correct
15 Correct 18 ms 7036 KB Output is correct
16 Correct 19 ms 4692 KB Output is correct
17 Correct 106 ms 28092 KB Output is correct
18 Correct 80 ms 27628 KB Output is correct
19 Correct 72 ms 25976 KB Output is correct
20 Correct 63 ms 23756 KB Output is correct
21 Correct 172 ms 64060 KB Output is correct
22 Correct 179 ms 61836 KB Output is correct
23 Correct 216 ms 53324 KB Output is correct
24 Correct 165 ms 62684 KB Output is correct
25 Correct 418 ms 109864 KB Output is correct
26 Correct 648 ms 134376 KB Output is correct
27 Correct 659 ms 139352 KB Output is correct
28 Correct 674 ms 124352 KB Output is correct
29 Correct 648 ms 121924 KB Output is correct
30 Correct 649 ms 124232 KB Output is correct
31 Correct 427 ms 70984 KB Output is correct
32 Correct 644 ms 132496 KB Output is correct