Submission #365609

#	Time	Username	Problem	Language	Result	Execution time	Memory
365609		jpark9013	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	1449 ms	314400 KiB

tracks

//Alt-Z on selected lines will collapse them
//Alt-Z on an indented block's top line will collapse that block
//Alt-Z on a folded block will expand it
//Alt-X will collapse all blocks on the deepest indention column (you can keep pressing Alt-X until all indention levels are folded)
//Shift-Alt-X will expand all the collapsed blocks

#include <bits/stdc++.h>
#include <cassert>
#define all(x) x.begin(), x.end()
#define debug(x) cerr << "[" << (#x) << " is " << (x) << "] "
#define debugl(x) cerr << "[" << (#x) << " is " << (x) << "]" << endl
#define eb emplace_back
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define len(x) ((int) sizeof(x)/sizeof(x[0]))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define mp make_pair
#define output_time cerr << "Time elapsed: " << 1000*clock() / CLOCKS_PER_SEC << "ms" << endl
#define pb push_back
#define sep cerr << "-----------------------------" << endl
#define test_cases int MMR; cin>>MMR; for (int i = 0; i < MMR; i++) solve()
#define test_input freopen("input.txt", "r", stdin)
#define test_local freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr)
using ld = long double;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using namespace std;
using pii = pair<int, int>;
using pld = pair<ld, ld>;
using pll = pair<ll, ll>;
template<class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using maxpq = priority_queue<T, vector<T>>;

const int INTMAX = 2147483647;
const int INTMIN = -2147483647;
const ll LLMAX = 9223372036854775807;
const ll LLMIN = -9223372036854775807;
const ll MOD = 1000000007;
const ll MOD998 = 998224353;
const ld pi = 3.1415926535897932385;


struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
template<typename K, typename V> using umap = unordered_map<K, V, custom_hash>;
template<typename K, typename V> using umultimap = unordered_multimap<K, V, custom_hash>;
template<typename T> using uset = unordered_set<T, custom_hash>;
template<typename T> using umultiset = unordered_multiset<T, custom_hash>;

void open(const string& s) {
  string a = s + ".in";
  string b = s + ".out";
  freopen(a.c_str(), "r", stdin);
  freopen(b.c_str(), "w", stdout);
}
template<typename A, typename B> ostream& operator<<(ostream &out, pair<A, B> const &pair);
template<typename T> ostream& operator<<(ostream &out, uset<T> const &s);
template<typename T> ostream& operator<<(ostream &out, set<T> const &s);
template<typename T> ostream& operator<<(ostream &out, multiset<T> const &s);
template<typename T> ostream& operator<<(ostream &out, umultiset<T> const &s);
template<typename K, typename V> ostream& operator<<(ostream &out, multimap<K, V> const &m);
template<typename K, typename V> ostream& operator<<(ostream &out, umultimap<K, V> const &m);
template<typename T> ostream& operator<<(ostream &out, vector<T> const &v);
template<typename K, typename V> ostream& operator<<(ostream &out, map<K, V> const &m);
template<typename K, typename V> ostream& operator<<(ostream &out, umap<K, V> const &m);
template<typename A, typename B> ostream& operator<<(ostream &out, pair<A, B> const &pair) {
  out << "(" << pair.first << ", " << pair.second;
  return out << ")";
}
template<typename T> ostream& operator<<(ostream &out, uset<T> const &s) {
  out << "["; int c = 0;
  for (T &i : s) {if (c) out << ", "; out << i; c++;}
  return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, set<T> const &s) {
  out << "["; int c = 0;
  for (T &i : s) {if (c) out << ", "; out << i; c++;}
  return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, vector<T> const &v) {
  out << "[";
  for (int i = 0; i < v.size(); i++) {if (i) out << ", "; out << v[i];}
  return out << "]";
}
template<typename K, typename V> ostream& operator<<(ostream &out, map<K, V> const &m) {
  out << "{"; int c = 0;
  for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
  return out << "}";
}
template<typename K, typename V> ostream& operator<<(ostream &out, umap<K, V> const &m) {
  out << "{"; int c = 0;
  for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
  return out << "}";
}
template<typename T> ostream& operator<<(ostream &out, multiset<T> const &s) {
  out << "["; int c = 0;
  for (T &i : s) {if (c) out << ", "; out << i; c++;}
  return out << "]";
}
template<typename T> ostream& operator<<(ostream &out, umultiset<T> const &s) {
  out << "["; int c = 0;
  for (T &i : s) {if (c) out << ", "; out << i; c++;}
  return out << "]";
}
template<typename K, typename V> ostream& operator<<(ostream &out, multimap<K, V> const &m) {
  out << "{"; int c = 0;
  for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
  return out << "}";
}
template<typename K, typename V> ostream& operator<<(ostream &out, umultimap<K, V> const &m) {
  out << "{"; int c = 0;
  for (const auto &pair : m) {if (c) out << ", "; out << pair.first << "=" << pair.second; c++;}
  return out << "}";
}
template<typename T> void next_vec(vector<T> &vec, int l) {
  vec = vector<T>(l);
  for (int i = 0; i < l; i++) cin >> vec[i];
}
template<typename A, typename B> void next_vec(vector<pair<A, B>> &vec, int l) {
  vec = vector<pair<A, B>>(l);
  for (int i = 0; i < l; i++) {
    A a; B b; cin >> a >> b;
    vec[i].first = a; vec[i].second = b;
  }
}
template<typename T> void next_graph(vector<vector<T>> &adj, int l) {
  adj = vector<vector<int>>(l);
  for (int i = 0; i < l; i++) {
    int a, b; cin >> a >> b;
    a--; b--;
    adj[a].pb(b);
    adj[b].pb(a);
  }
}
string join(vector<string> &vec, string &t) {
  int l = vec.size();
  string s;
  for (int i = 0; i < l; i++) {
    s += vec[i];
    if (i != l-1) s += t;
  }
  return s;
}
ll combo(ll n, ll d) {
  if (d > n) return 0;
  if (d*2 > n) d = n-d;
  if (d == 0) return 1;
  ll res = n;
  for (ll i = 2; i <= d; i++) {
    res *= (n-i+1);
    res /= i;
  }
  return res;
}
template<typename T> void shuffle_vec(vector<T> &vec) {
  shuffle(vec.begin(), vec.end(), mt19937(random_device()()));
}
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a%b);}
ll lcm(ll a, ll b) {return a/gcd(a, b)*b;}
vector<string> split(const string& str, const string& delim = " ") {
  vector<string> tokens;
  size_t prev = 0, pos = 0;
  do {
    pos = str.find(delim, prev);
    if (pos == string::npos) pos = str.length();
    string token = str.substr(prev, pos-prev);
    if (!token.empty()) tokens.push_back(token);
    prev = pos + delim.length();
  }
  while (pos < str.length() && prev < str.length());
  return tokens;
}
template<typename T> int binary_search(vector<T> &vec, T &n) {
  int l = vec.size();
  int left = 0;
  int right = l-1;
  while (left != right) {
    int mid = (left+right+1)/2;
    if (vec[mid] > n) right = mid-1;
    else left = mid;
  }
  return vec[left] == n ? left : -1;
}
template<typename T> vector<ll> prefix(vector<T> &vec) {
  int l = vec.size(); assert(l);
  vector<ll> pre(l); pre[0] = vec[0];
  for (int i = 1; i < l; i++) pre[i] = pre[i-1]+vec[i];
  return pre;
}
template<typename T> vector<ll> suffix(vector<T> &vec) {
  int l = vec.size();
  assert(l);
  vector<ll> suf(l);
  suf[l-1] = vec[l-1];
  for (int i = l - 2; i >= 0; i--) suf[i] = suf[i+1] + vec[i];
  return suf;
}
ll bs_lowest(const function<bool(ll)> &f, ll lo, ll hi) {
  while (lo < hi) {
    ll mid = (lo+hi)/2;
    f(mid) ? hi = mid : lo = mid+1;
  }
  return lo;
}
ll bs_highest(const function<bool(ll)> &f, ll lo, ll hi) {
  ll a = lo;
  for (ll i = hi; i >= a; i /= 2) {
    while (f(lo + i)) lo += i;
  }
  return lo;
}
template<typename T> T min(vector<T> &vec) {
  assert(!vec.empty());
  T a = vec[0];
  for (T &i : vec) a = min(a, i);
  return a;
}
template<typename T> T max(vector<T> &vec) {
  assert(!vec.empty());
  T a = vec[0];
  for (T &i : vec) a = max(a, i);
  return a;
}
template<typename T> ll sum(vector<T> &vec) {
  ll sum = 0;
  for (T &i : vec) sum += i;
  return sum;
}
vector<bool> sieve(int n) {
  vector<bool> vec(n+1, true);
  vec[0] = false;
  vec[1] = false;
  for (int i = 2; i <= n; i++) {
    if (vec[i]) {
      for (int j = i; j <= n; j += i) vec[i] = false;
    }
  }
  return vec;
}
bool prime(ll n) {
	for (ll i = 2; i*i <= n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

template <int MOD_> struct modnum {
  template<typename T>
  modnum(T value) {
    v = value % MOD_;
    if (v < 0) v += MOD_;
  }

  static constexpr int MOD = MOD_;
  static_assert(MOD_ > 0, "MOD must be positive");

  int v;
  private:
  using ll = long long;

  static int minv(int a, int m) {
    a %= m;
    assert(a);
    return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  }

  public:

  modnum() : v(0) {}
  explicit modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  explicit operator int() const { return v; }
  explicit operator long long() const { return v; }
  explicit operator unsigned int() const { return v; }
  explicit operator unsigned long long() const { return v; }
  friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

  friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  friend bool operator <= (const modnum& a, const modnum& b) { return a.v <= b.v; }
  friend bool operator >= (const modnum& a, const modnum& b) { return a.v >= b.v; }
  friend bool operator > (const modnum& a, const modnum& b) { return a.v > b.v; }
  friend bool operator < (const modnum& a, const modnum& b) { return a.v < b.v; }
  template<typename T>
  friend bool operator == (const modnum& a, const T& b) {return a.v == b;}
  template<typename T>
  friend bool operator != (const modnum& a, const T& b) {return a.v != b;}
  template<typename T>
  friend bool operator >= (const modnum& a, const T& b) {return a.v >= b;}
  template<typename T>
  friend bool operator <= (const modnum& a, const T& b) {return a.v <= b;}
  template<typename T>
  friend bool operator > (const modnum& a, const T& b) {return a.v > b;}
  template<typename T>
  friend bool operator < (const modnum& a, const T& b) {return a.v < b;}

  modnum inv() const {
    modnum res;
    res.v = minv(v, MOD);
    return res;
  }
  friend modnum inv(const modnum& m) { return m.inv(); }
  modnum neg() const {
    modnum res;
    res.v = v ? MOD-v : 0;
    return res;
  }
  friend modnum neg(const modnum& m) { return m.neg(); }

  modnum operator- () const {
    return neg();
  }
  modnum operator+ () const {
    return modnum(*this);
  }

  modnum& operator ++ () {
    v ++;
    if (v == MOD) v = 0;
    return *this;
  }
  modnum& operator -- () {
    if (v == 0) v = MOD;
    v --;
    return *this;
  }
  modnum& operator += (const modnum& o) {
    v -= MOD-o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator -= (const modnum& o) {
    v -= o.v;
    v = (v < 0) ? v + MOD : v;
    return *this;
  }
  modnum& operator *= (const modnum& o) {
    v = int(ll(v) * ll(o.v) % MOD);
    return *this;
  }
  modnum& operator /= (const modnum& o) {
    return *this *= o.inv();
  }

  friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

template <typename T> T power(T a, ll b) {
  assert(b >= 0);
  T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

using mod = modnum<(int) 1e9+7>;

#define inf 1e9

int h, w;
vector<string> vec;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
vector<vector<int>> dis;
vector<vector<bool>> seen;

bool valid(int i, int j) {return i >= 0 && i < h && j >= 0 && j < w && vec[i][j] != '.';}

int bfs() {
	deque<pii> d;
	d.pb(mp(0, 0));
	while (!d.empty()) {
		pii cur = d.front();
		d.pop_front();
		int i = cur.first, j = cur.second;
		if (seen[i][j]) continue;
		seen[i][j] = true;
		for (int k = 0; k < 4; k++) {
			int a = i+dy[k], b = j+dx[k];
			if (valid(a, b)) {
				if (vec[a][b] != vec[i][j]) {
					dis[a][b] = min(dis[a][b], dis[i][j]+1);
					d.pb(mp(a, b));
				}
				else {
					dis[a][b] = min(dis[a][b], dis[i][j]);
					d.push_front(mp(a, b));
				} 
			}
		}
	}
	return dis[h-1][w-1];
}

void solve() {
	cin >> h >> w;
	vec = vector<string>(h);
	dis = vector<vector<int>>(h, vector<int>(w, inf));
	seen = vector<vector<bool>>(h, vector<bool>(w));
	dis[0][0] = 0;
	for (int i = 0; i < h; i++) cin >> vec[i];
	int a = 0, b = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (vec[i][j] == 'R') a = 1;
			else if (vec[i][j] == 'F') b = 1;	
		}
	}
	cout << a+b+bfs() << endl;
}

int main() {
  FAST_IO;
 	//test_input;
 	//test_local;
  //open("nocross");
  solve();
  output_time;
}

Compilation message (stderr)

tracks.cpp: In function 'void open(const string&)':
tracks.cpp:64:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   freopen(a.c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:65:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   freopen(b.c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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