oj.uz

Submission #448685

# Submission time Handle Problem Language Result Execution time Memory
448685 2021-07-31T16:45:27 Z Christopher_ Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 643 ms 131124 KB 
#include <bits/stdc++.h>

using namespace std;


int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

        int n, m;
        cin >> n >> m;
        vector<string> mat(n);
        vector<vector<int>> dist(n, vector<int>(m));
        for (int i = 0; i < n; ++i) {
                cin >> mat[i];
        }

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

        auto Check = [&](int x, int y) {
                return x >= 0 && x < n && y >= 0 && y < m && mat[x][y] != '.' && dist[x][y] == 0;
        };

        int ans = 0;
        while (!q.empty()) {
                int x = q.front().first, y = q.front().second; q.pop_front();
                ans = max(ans, dist[x][y]);
                for (int k = 0; k < 4; ++k) {
                        int nx = x + dx[k], ny = y + dy[k];
                        if (Check(nx, ny)) {
                                if (mat[nx][ny] == mat[x][y]) {
                                        dist[nx][ny] = dist[x][y];
                                        q.push_front({nx, ny});
                                } else {
                                        dist[nx][ny] = dist[x][y] + 1;
                                        q.push_back({nx, ny});
                                }
                        }
                }
        }
        cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1740 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 6 ms 1476 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 4 ms 892 KB Output is correct
13 Correct 2 ms 716 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 9 ms 1752 KB Output is correct
16 Correct 11 ms 1840 KB Output is correct
17 Correct 7 ms 1776 KB Output is correct
18 Correct 6 ms 1356 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 34 ms 9692 KB Output is correct
3 Correct 196 ms 96628 KB Output is correct
4 Correct 55 ms 22632 KB Output is correct
5 Correct 120 ms 54176 KB Output is correct
6 Correct 635 ms 110544 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 820 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 37 ms 9680 KB Output is correct
14 Correct 20 ms 5764 KB Output is correct
15 Correct 15 ms 6220 KB Output is correct
16 Correct 19 ms 4176 KB Output is correct
17 Correct 91 ms 24576 KB Output is correct
18 Correct 63 ms 24248 KB Output is correct
19 Correct 54 ms 22728 KB Output is correct
20 Correct 45 ms 20932 KB Output is correct
21 Correct 115 ms 56084 KB Output is correct
22 Correct 122 ms 54180 KB Output is correct
23 Correct 185 ms 46788 KB Output is correct
24 Correct 116 ms 54696 KB Output is correct
25 Correct 403 ms 96620 KB Output is correct
26 Correct 397 ms 124040 KB Output is correct
27 Correct 537 ms 131124 KB Output is correct
28 Correct 639 ms 110648 KB Output is correct
29 Correct 643 ms 108196 KB Output is correct
30 Correct 578 ms 113724 KB Output is correct
31 Correct 454 ms 62280 KB Output is correct
32 Correct 472 ms 120832 KB Output is correct