oj.uz

Submission #725753

# Submission time Handle Problem Language Result Execution time Memory
725753 2023-04-18T02:14:03 Z asdfgrace Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 562 ms 107600 KB 
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << "  "); PRINT("}\n");)
using i64 = int64_t;
const int INF = 1000000007; //998244353
 
struct S {
  int n, m;
  array<array<char, 4000>, 4000> a{};
  array<array<bool, 4000>, 4000> visited{};
 
  void run() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cin >> a[i][j];
      }
    }
  }
  
  void bfs() {
    deque<array<int, 3>> q; // {d, x, y}
    q.push_back({1, 0, 0});
    visited[0][0] = true;
    int ans = 1;
    while (!q.empty()) {
      int x = q.front()[1];
      int y = q.front()[2];
      int d = q.front()[0];
      q.pop_front();
      ans = max(ans, d);
      PV(x); PV(y); PV(d); PRINT('\n');
      char c = a[x][y];
      int a1 = ok(x, y + 1, c);
      if (a1 >= 0) {
        if (a1 == 1) q.push_back({d + 1, x, y + 1});
        else q.push_front({d, x, y + 1});
        visited[x][y + 1] = true;
      }
      int a2 = ok(x, y - 1, c);
      if (a2 >= 0) {
        if (a2 == 1) q.push_back({d + 1, x, y - 1});
        else q.push_front({d, x, y - 1});
        visited[x][y - 1] = true;
      }
      int a3 = ok(x + 1, y, c);
      if (a3 >= 0) {
        if (a3 == 1) q.push_back({d + 1, x + 1, y});
        else q.push_front({d, x + 1, y});
        visited[x + 1][y] = true;
      }
      int a4 = ok(x - 1, y, c);
      if (a4 >= 0) {
        if (a4 == 1) q.push_back({d + 1, x - 1, y});
        else q.push_front({d, x - 1, y});
        visited[x - 1][y] = true;
      }
    }
    cout << ans << '\n';
  }
  
  int ok(int x, int y, char c) {
    if (x < 0 || x >= n) return -1;
    if (y < 0 || y >= m) return -1;
    if (visited[x][y]) return -1;
    if (a[x][y] == '.') return -1;
    return (a[x][y] == c ? 0 : 1);
  }
  
  
};
 
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  auto sol = make_unique<S>();
  sol->run();
  sol->bfs();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31916 KB Output is correct
2 Correct 13 ms 31572 KB Output is correct
3 Correct 17 ms 31580 KB Output is correct
4 Correct 19 ms 32040 KB Output is correct
5 Correct 16 ms 31656 KB Output is correct
6 Correct 14 ms 31572 KB Output is correct
7 Correct 14 ms 31648 KB Output is correct
8 Correct 14 ms 31572 KB Output is correct
9 Correct 15 ms 31628 KB Output is correct
10 Correct 15 ms 31600 KB Output is correct
11 Correct 16 ms 31684 KB Output is correct
12 Correct 17 ms 31676 KB Output is correct
13 Correct 16 ms 31656 KB Output is correct
14 Correct 20 ms 31772 KB Output is correct
15 Correct 25 ms 31828 KB Output is correct
16 Correct 22 ms 31940 KB Output is correct
17 Correct 20 ms 31780 KB Output is correct
18 Correct 19 ms 32076 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31572 KB Output is correct
2 Correct 66 ms 32660 KB Output is correct
3 Correct 288 ms 33384 KB Output is correct
4 Correct 102 ms 33000 KB Output is correct
5 Correct 196 ms 33484 KB Output is correct
6 Correct 547 ms 52952 KB Output is correct
7 Correct 15 ms 31572 KB Output is correct
8 Correct 18 ms 31700 KB Output is correct
9 Correct 16 ms 31652 KB Output is correct
10 Correct 14 ms 31572 KB Output is correct
11 Correct 15 ms 31648 KB Output is correct
12 Correct 14 ms 31616 KB Output is correct
13 Correct 59 ms 32644 KB Output is correct
14 Correct 35 ms 32228 KB Output is correct
15 Correct 34 ms 32424 KB Output is correct
16 Correct 33 ms 32136 KB Output is correct
17 Correct 117 ms 33124 KB Output is correct
18 Correct 88 ms 33024 KB Output is correct
19 Correct 93 ms 32980 KB Output is correct
20 Correct 77 ms 33016 KB Output is correct
21 Correct 176 ms 33544 KB Output is correct
22 Correct 202 ms 33532 KB Output is correct
23 Correct 208 ms 33484 KB Output is correct
24 Correct 199 ms 33500 KB Output is correct
25 Correct 303 ms 33356 KB Output is correct
26 Correct 490 ms 107600 KB Output is correct
27 Correct 512 ms 60352 KB Output is correct
28 Correct 562 ms 53140 KB Output is correct
29 Correct 548 ms 49716 KB Output is correct
30 Correct 527 ms 59100 KB Output is correct
31 Correct 429 ms 34172 KB Output is correct
32 Correct 476 ms 58388 KB Output is correct