oj.uz

Submission #1092784

# Submission time Handle Problem Language Result Execution time Memory
1092784 2024-09-25T04:27:33 Z juicy Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 780 ms 174404 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vector a(n, vector<char>(m));
  for (int i = 0; i < n; ++i) {
    for (auto &c : a[i]) {
      cin >> c;
    }
  }
  vector d(n, vector<int>(m, 1e9));
  vector vis(n, vector<bool>(m));
  auto inside = [&](int r, int c) {
    return 0 <= r && r < n && 0 <= c && c < m && a[r][c] != '.' && !vis[r][c];
  }; 
  deque<array<int, 2>> dq{{0, 0}};
  d[0][0] = 1;
  int res = 0;
  while (dq.size()) {
    auto [r, c] = dq.front(); dq.pop_front();
    if (vis[r][c]) {
      continue;
    }
    res = d[r][c];
    vis[r][c] = 1;
    for (int k = 0; k < 4; ++k) {
      int i = r + dx[k], j = c + dy[k];
      if (inside(i, j)) {
        if (a[r][c] == a[i][j]) {
          d[i][j] = min(d[i][j], d[r][c]);
          dq.push_front({i, j});
        } else {
          d[i][j] = min(d[i][j], d[r][c] + 1);
          dq.push_back({i, j});
        }
      }
    }
  }
  cout << res;
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1880 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 1844 KB Output is correct
5 Correct 2 ms 1016 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 7 ms 860 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 10 ms 1884 KB Output is correct
16 Correct 16 ms 2092 KB Output is correct
17 Correct 8 ms 2044 KB Output is correct
18 Correct 6 ms 1748 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 44 ms 9820 KB Output is correct
3 Correct 267 ms 96744 KB Output is correct
4 Correct 67 ms 23124 KB Output is correct
5 Correct 164 ms 54608 KB Output is correct
6 Correct 780 ms 122592 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 47 ms 9996 KB Output is correct
14 Correct 24 ms 5980 KB Output is correct
15 Correct 17 ms 6488 KB Output is correct
16 Correct 22 ms 4188 KB Output is correct
17 Correct 123 ms 24960 KB Output is correct
18 Correct 66 ms 24660 KB Output is correct
19 Correct 68 ms 23172 KB Output is correct
20 Correct 60 ms 21072 KB Output is correct
21 Correct 158 ms 56512 KB Output is correct
22 Correct 149 ms 54516 KB Output is correct
23 Correct 217 ms 47188 KB Output is correct
24 Correct 139 ms 55120 KB Output is correct
25 Correct 320 ms 96596 KB Output is correct
26 Correct 422 ms 174404 KB Output is correct
27 Correct 617 ms 161484 KB Output is correct
28 Correct 779 ms 122456 KB Output is correct
29 Correct 727 ms 120656 KB Output is correct
30 Correct 701 ms 130108 KB Output is correct
31 Correct 588 ms 62936 KB Output is correct
32 Correct 541 ms 143020 KB Output is correct