oj.uz

Submission #895478

# Submission time Handle Problem Language Result Execution time Memory
895478 2023-12-30T02:32:23 Z kevinlu Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 397 ms 130696 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '"' << x << '"'; }
void __print(const string &x) { cerr << '"' << x << '"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)             \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define debug(x...)
#endif

void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if ((int)s.size()) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}

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

int depth[4000][4000];
string snow[4000];

int main() {
  // 0/1 bfs
  setIO();
  int h, w;
  cin >> h >> w;
  for (int i = 0; i < h; i++) {
    cin >> snow[i];
  }
  deque<pi> dq;
  dq.push_back({0, 0});
  depth[0][0] = 1;
  int ans = 0;
  while (!dq.empty()) {
    pi top = dq.front();
    dq.pop_front();
    ans = max(ans, depth[top.f][top.s]);
    for (int k = 0; k < 4; k++) {
      int nx = top.f + dx[k], ny = top.s + dy[k];
      if (nx < 0 || nx >= h || ny < 0 || ny >= w || depth[nx][ny] != 0 || snow[nx][ny] == '.') {
        continue;
      }
      if (snow[nx][ny] == snow[top.f][top.s]) {
        depth[nx][ny] = depth[top.f][top.s];
        dq.push_front({nx, ny});
      } else {
        depth[nx][ny] = depth[top.f][top.s] + 1;
        dq.push_back({nx, ny});
      }
    }
  }
  cout << ans;
  return 0;
}

Compilation message

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3932 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 5 ms 3672 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1672 KB Output is correct
12 Correct 3 ms 2140 KB Output is correct
13 Correct 2 ms 2136 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 8 ms 3776 KB Output is correct
16 Correct 11 ms 3932 KB Output is correct
17 Correct 6 ms 3808 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16372 KB Output is correct
2 Correct 26 ms 11872 KB Output is correct
3 Correct 145 ms 75500 KB Output is correct
4 Correct 42 ms 29436 KB Output is correct
5 Correct 116 ms 51212 KB Output is correct
6 Correct 360 ms 110060 KB Output is correct
7 Correct 7 ms 16984 KB Output is correct
8 Correct 7 ms 16220 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 832 KB Output is correct
11 Correct 7 ms 16352 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 27 ms 11896 KB Output is correct
14 Correct 15 ms 8028 KB Output is correct
15 Correct 12 ms 10448 KB Output is correct
16 Correct 13 ms 4996 KB Output is correct
17 Correct 79 ms 25608 KB Output is correct
18 Correct 49 ms 32412 KB Output is correct
19 Correct 41 ms 29348 KB Output is correct
20 Correct 36 ms 22356 KB Output is correct
21 Correct 88 ms 50568 KB Output is correct
22 Correct 115 ms 51256 KB Output is correct
23 Correct 138 ms 42384 KB Output is correct
24 Correct 88 ms 47516 KB Output is correct
25 Correct 331 ms 96368 KB Output is correct
26 Correct 253 ms 130696 KB Output is correct
27 Correct 279 ms 123176 KB Output is correct
28 Correct 363 ms 110024 KB Output is correct
29 Correct 397 ms 108400 KB Output is correct
30 Correct 323 ms 112544 KB Output is correct
31 Correct 311 ms 71964 KB Output is correct
32 Correct 238 ms 108168 KB Output is correct