oj.uz

Submission #842602

# Submission time Handle Problem Language Result Execution time Memory
842602 2023-09-03T05:33:07 Z Qang Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 423 ms 118852 KB 
#include <bits/stdc++.h> // 0/1 BFS
using namespace std;
#define MAXN 4001
string g[MAXN];
int n, m, depth[MAXN][MAXN], dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; 

bool inside(int i, int j) {
    return i >= 0 && i < n && j >= 0 && j < m && g[i][j] != '.';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> g[i];
    depth[0][0] = 1; //depth[i][j] = 0 means unvisited
    deque<pair<int, int>> q;
    q.push_back({ 0, 0 });
    int ans = 1;
    while (!q.empty()) {
        auto z = q.front();
        q.pop_front();
        ans = max(ans, depth[z.first][z.second]);
        for (int i = 0; i < 4; ++i) {
            int f = z.first + dx[i], s = z.second + dy[i];
            if (inside(f, s) && depth[f][s] == 0) {
                if (g[f][s] == g[z.first][z.second]) {
                    depth[f][s] = depth[z.first][z.second];
                    q.push_front({ f, s });
                }
                else {
                    depth[f][s] = depth[z.first][z.second] + 1;
                    q.push_back({ f, s });
                }
            }
        }
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3672 KB Output is correct
2 Correct 0 ms 632 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 5 ms 3416 KB Output is correct
5 Correct 2 ms 1880 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 600 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 2 ms 1624 KB Output is correct
12 Correct 3 ms 2136 KB Output is correct
13 Correct 2 ms 1884 KB Output is correct
14 Correct 2 ms 1880 KB Output is correct
15 Correct 7 ms 3416 KB Output is correct
16 Correct 8 ms 3672 KB Output is correct
17 Correct 6 ms 3416 KB Output is correct
18 Correct 4 ms 3420 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15960 KB Output is correct
2 Correct 25 ms 10320 KB Output is correct
3 Correct 136 ms 59788 KB Output is correct
4 Correct 41 ms 25680 KB Output is correct
5 Correct 107 ms 42764 KB Output is correct
6 Correct 416 ms 95420 KB Output is correct
7 Correct 7 ms 16728 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 7 ms 16472 KB Output is correct
12 Correct 1 ms 1112 KB Output is correct
13 Correct 25 ms 10588 KB Output is correct
14 Correct 15 ms 7000 KB Output is correct
15 Correct 12 ms 9304 KB Output is correct
16 Correct 13 ms 4440 KB Output is correct
17 Correct 67 ms 21328 KB Output is correct
18 Correct 49 ms 28240 KB Output is correct
19 Correct 41 ms 25680 KB Output is correct
20 Correct 34 ms 19024 KB Output is correct
21 Correct 86 ms 41532 KB Output is correct
22 Correct 112 ms 42732 KB Output is correct
23 Correct 130 ms 34964 KB Output is correct
24 Correct 85 ms 38992 KB Output is correct
25 Correct 306 ms 81040 KB Output is correct
26 Correct 214 ms 118852 KB Output is correct
27 Correct 303 ms 110188 KB Output is correct
28 Correct 423 ms 95400 KB Output is correct
29 Correct 403 ms 91512 KB Output is correct
30 Correct 363 ms 99088 KB Output is correct
31 Correct 320 ms 62100 KB Output is correct
32 Correct 288 ms 100328 KB Output is correct