Submission #1236219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236219		chrwn	Tracks in the Snow (BOI13_tracks)	C++20	19.79 / 100	1453 ms	455428 KiB

tracks

#include <bits/stdc++.h>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;

#define f first
#define s second
#define mod(a, b) (((a)%(b)+(b))%(b))
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
tree_order_statistics_node_update>;

const ll MAX_N = 1e5 + 5;
const ll MOD = 1e9+7;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

void setio(string s="") {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  if (size(s)) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
  }
}

#ifdef LOCAL
  #include "debug.h"
#endif

void solve() {
  ll n,m; cin >> n >> m;
  vector<vector<ll>> v(n,vector<ll>(m));
  for (auto &i : v) {
    for (auto &j : i) {
      char c; cin >> c;
      j=(c=='F');
    }
  }
  deque<pair<ll,pair<ll,ll>>> q;
  q.push_front({0,{0,0}});
  ll ans=0;
  vector<vector<ll>> dist(n,vector<ll>(m,1e18));
  dist[0][0]=0;
  while (!q.empty()) {
    auto [w,p]=q.front(); q.pop_front();
    ll r=p.f, c=p.s;
    if (dist[r][c]!=w) continue;
    chmax(ans,w);
    auto ad = [&](ll dr, ll dc, ll w) {
      ll nr=r+dr, nc=c+dc;
      if (nr<0 || nr>=n || nc<0 || nc>=m) return;
      ll nw=w;
      nw += v[r][c]^v[nr][c];
      nw += v[r][c]^v[r][nc];
      if (dist[nr][nc]>nw) {
        dist[nr][nc]=nw;
        if (nw-w) q.push_back({nw,{nr,nc}});
        else q.push_front({nw,{nr,nc}});
      }
    };
    for (ll i=0; i<4; ++i) {
      ad(dy[i],dx[i],w);
    }
  }
  cout << ans+1 << '\n';
}

signed main() {
  setio();
  ll tc = 1;
  // cin >> tc;
  while (tc--) {
    // cout << "tc 1:\n";
    solve();
  }
}

Compilation message (stderr)

tracks.cpp: In function 'void setio(std::string)':
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((s+".in").c_str(),"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((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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