Submission #652707

#	Time	Username	Problem	Language	Result	Execution time	Memory
652707		chanhchuong123	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	783 ms	152728 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}

const int dx[] = {-1, 0, 0, +1};
const int dy[] = {0, -1, +1, 0};
const int N = 4004;
int n, m;
int ans;
int d[N][N];
char a[N][N];
bool vis[N][N];

main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(task".inp","r")) {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }

  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      cin >> a[i][j];
  memset(d, 0x3f, sizeof(d));
  deque<pair<int, int>> dq;
  dq.push_back({1, 1});
  d[1][1] = 1;
  while (dq.size()) {
    auto [x, y] = dq.front();
    dq.pop_front();
    if (vis[x][y]) continue;
    vis[x][y] = 1; maxi(ans, d[x][y]);
    for (int i = 0; i < 4; i++) {
      int u = x + dx[i], v = y + dy[i];
      if (u < 1 || u > n) continue;
      if (v < 1 || v > m) continue;
      if (a[u][v] == '.') continue;
      int w = a[u][v] != a[x][y];
      if (mini(d[u][v], d[x][y] + w)) {
        if (w) dq.push_back({u, v});
        else dq.push_front({u, v});
      }
    }
  }
  cout << ans;
}

Compilation message (stderr)

tracks.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main() {
      | ^~~~
tracks.cpp: In function 'int main()':
tracks.cpp:43:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     auto [x, y] = dq.front();
      |          ^
tracks.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:31:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70