Submission #365609

#TimeUsernameProblemLanguageResultExecution timeMemory
365609jpark9013Tracks in the Snow (BOI13_tracks)C++17
2.19 / 100
1449 ms314400 KiB
//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);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...