oj.uz

Submission #713260

# Submission time Handle Problem Language Result Execution time Memory
713260 2023-03-21T14:36:25 Z cfjason Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 1016 ms 147068 KB 
#include <bits/stdc++.h>
#define INF 2147483647
using namespace std;
vector<array<int, 2>> offsets = {
  {0, -1},
  {0, 1},
  {-1, 0},
  {1, 0}
};
int main (int argc, char *argv[])
{
  int h, w;
  cin >> h >> w;
  vector<string> grid(h);
  for (int i = 0; i < h; i++) {
    cin >> grid[i];
  }
  vector<vector<int>> distance(h, vector<int>(w, INF));
  deque<array<int, 2>> toVisit;
  toVisit.push_front({0, 0});
  distance[0][0] = 0;
  int result = 0;
  while (!toVisit.empty()) {
    auto tp = toVisit.front();
    toVisit.pop_front();
    for (auto offset : offsets) {
      int x = tp[0] + offset[0];
      int y = tp[1] + offset[1];
      if(x < 0 || x >=h || y < 0 || y >= w) continue;
      array<int, 2> pos = {x, y};
      if(distance[tp[0]][tp[1]] + (grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]]) < distance[pos[0]][pos[1]]){
        distance[pos[0]][pos[1]] = distance[tp[0]][tp[1]] + (grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]]) ;
        result = std::max(result, distance[pos[0]][pos[1]]);
        if((grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]])){
          toVisit.push_back(pos);
        }
        else {
          toVisit.push_front(pos);
        }
      }
    }
  }
  cout << result << endl;
  return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2004 KB Output isn't correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 8 ms 1540 KB Output isn't correct
5 Incorrect 5 ms 852 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 4 ms 824 KB Output isn't correct
11 Incorrect 3 ms 516 KB Output isn't correct
12 Incorrect 6 ms 852 KB Output isn't correct
13 Incorrect 5 ms 916 KB Output isn't correct
14 Incorrect 5 ms 852 KB Output isn't correct
15 Incorrect 15 ms 2512 KB Output isn't correct
16 Incorrect 14 ms 2040 KB Output isn't correct
17 Incorrect 13 ms 2004 KB Output isn't correct
18 Incorrect 8 ms 1492 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 852 KB Output isn't correct
2 Incorrect 79 ms 14040 KB Output isn't correct
3 Incorrect 734 ms 137704 KB Output isn't correct
4 Incorrect 225 ms 26776 KB Output isn't correct
5 Incorrect 384 ms 92940 KB Output isn't correct
6 Incorrect 899 ms 121896 KB Output isn't correct
7 Incorrect 3 ms 852 KB Output isn't correct
8 Incorrect 4 ms 856 KB Output isn't correct
9 Incorrect 4 ms 824 KB Output isn't correct
10 Incorrect 2 ms 596 KB Output isn't correct
11 Incorrect 4 ms 824 KB Output isn't correct
12 Incorrect 2 ms 440 KB Output isn't correct
13 Incorrect 75 ms 14204 KB Output isn't correct
14 Incorrect 44 ms 8644 KB Output isn't correct
15 Incorrect 49 ms 9676 KB Output isn't correct
16 Incorrect 31 ms 5708 KB Output isn't correct
17 Incorrect 194 ms 37596 KB Output isn't correct
18 Incorrect 232 ms 36644 KB Output isn't correct
19 Incorrect 193 ms 26836 KB Output isn't correct
20 Incorrect 158 ms 30292 KB Output isn't correct
21 Incorrect 413 ms 74956 KB Output isn't correct
22 Incorrect 385 ms 92988 KB Output isn't correct
23 Incorrect 365 ms 66648 KB Output isn't correct
24 Incorrect 385 ms 81604 KB Output isn't correct
25 Incorrect 1016 ms 147068 KB Output isn't correct
26 Incorrect 798 ms 123876 KB Output isn't correct
27 Incorrect 829 ms 128672 KB Output isn't correct
28 Incorrect 863 ms 121964 KB Output isn't correct
29 Incorrect 853 ms 120700 KB Output isn't correct
30 Incorrect 837 ms 119948 KB Output isn't correct
31 Incorrect 626 ms 63180 KB Output isn't correct
32 Incorrect 843 ms 122016 KB Output isn't correct