oj.uz

Submission #1062959

# Submission time Handle Problem Language Result Execution time Memory
1062959 2024-08-17T12:34:45 Z v_matei Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 51 ms 94556 KB 
#include <bits/stdc++.h>
#include <deque>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");

#define NMAX 4001
#define INF INT_MAX
int di[] = {0, 1, 0, -1}, dj[] = {-1, 0, 1, 0};

int h, w;
char map[NMAX][NMAX];

void citire() {
  std::cin >> h >> w;
  for (int i = 0; i < h; i++)
    std::cin >> map[i];
}

int dist[NMAX][NMAX];

bool inside(int i, int j) {
  return (i > -1 && i < h && j > -1 && j < w && map[i][j] != '.');
}

int bfs01() {
  std::deque<pii> q;
  q.push_back({0, 0});
  dist[0][0] = 1;
  int ans = 1;
  while (q.size()) {
    pii c = q.front();
    q.pop_front();
    ans = std::max(ans, dist[c.first][c.second]);

    for (int i = 0; i < 4; i++) {
      int x = c.first + di[i], y = c.second + dj[i];
      if (inside(x, y) && dist[x][y] == 0) {
        if (map[x][y] == map[c.first][c.second]) {
          dist[x][y] = dist[c.first][c.second];
          q.push_front({x, y});
        } else {
          dist[x][y] = dist[c.first][c.second] + 1;
          q.push_back({x, y});
        }
      }
    }
  }
  return ans;
}

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();

  for (int i = 1; i <= h; i++)
    for (int j = 1; j <= w; j++)
      dist[i][j] = INF;

  std::cout << bfs01();
  return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5468 KB Output isn't correct
2 Incorrect 0 ms 604 KB Output isn't correct
3 Incorrect 0 ms 860 KB Output isn't correct
4 Incorrect 3 ms 5000 KB Output isn't correct
5 Incorrect 2 ms 3164 KB Output isn't correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Incorrect 1 ms 860 KB Output isn't correct
8 Incorrect 1 ms 732 KB Output isn't correct
9 Incorrect 1 ms 1116 KB Output isn't correct
10 Incorrect 1 ms 2728 KB Output isn't correct
11 Incorrect 1 ms 2140 KB Output isn't correct
12 Incorrect 1 ms 3164 KB Output isn't correct
13 Incorrect 1 ms 3160 KB Output isn't correct
14 Incorrect 2 ms 3160 KB Output isn't correct
15 Incorrect 4 ms 5448 KB Output isn't correct
16 Incorrect 2 ms 5468 KB Output isn't correct
17 Incorrect 3 ms 5212 KB Output isn't correct
18 Incorrect 2 ms 4952 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 31068 KB Output isn't correct
2 Incorrect 8 ms 18012 KB Output isn't correct
3 Incorrect 51 ms 94556 KB Output isn't correct
4 Incorrect 15 ms 33620 KB Output isn't correct
5 Incorrect 33 ms 67892 KB Output isn't correct
6 Incorrect 47 ms 94292 KB Output isn't correct
7 Incorrect 11 ms 32344 KB Output isn't correct
8 Incorrect 15 ms 31068 KB Output isn't correct
9 Incorrect 1 ms 604 KB Output isn't correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Incorrect 11 ms 31836 KB Output isn't correct
12 Incorrect 1 ms 1632 KB Output isn't correct
13 Incorrect 8 ms 18020 KB Output isn't correct
14 Incorrect 5 ms 12132 KB Output isn't correct
15 Incorrect 5 ms 13108 KB Output isn't correct
16 Incorrect 3 ms 6752 KB Output isn't correct
17 Incorrect 17 ms 36040 KB Output isn't correct
18 Incorrect 18 ms 35680 KB Output isn't correct
19 Incorrect 15 ms 33640 KB Output isn't correct
20 Incorrect 14 ms 31056 KB Output isn't correct
21 Incorrect 35 ms 70488 KB Output isn't correct
22 Incorrect 32 ms 67940 KB Output isn't correct
23 Incorrect 32 ms 56892 KB Output isn't correct
24 Incorrect 30 ms 69392 KB Output isn't correct
25 Incorrect 44 ms 94288 KB Output isn't correct
26 Correct 37 ms 80928 KB Output is correct
27 Incorrect 45 ms 94332 KB Output isn't correct
28 Incorrect 45 ms 94168 KB Output isn't correct
29 Incorrect 45 ms 94392 KB Output isn't correct
30 Incorrect 44 ms 92604 KB Output isn't correct
31 Incorrect 34 ms 73000 KB Output isn't correct
32 Incorrect 43 ms 94140 KB Output isn't correct