Submission #499183

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
499183	2021-12-27T12:17:23 Z	jakubd	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	495 ms	123944 KB

tracks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define manytests int TT;cin >> TT; while (TT--)
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FORd(i,a,b) for (int i = (a); i >= (b); --i)
#define REP(i,a,b,c) for (int i = (a); i < (b); i += (c))
#define REPd(i,a,b,c) for (int i = (a); i >= (b); i -= (c))
 
#define ll long long
#define ld long double
#define str string
#define fi first
#define se second
#define rev reverse
 
int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1}, dy[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int INF = 1e9;
ll INFI = 1e18;
double PI = atan(1) * 4;
double eps = 1e-9;
// const int MOD = 1e9+7;
// const int MOD = 998244353;
const int MOD = 100000000;
 
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define vd vector<double>
#define vs vector<string>
#define vld vector<ld>
#define vb vector<bool>
#define vvi vector<vi>
#define vvl vector<vl>
#define pii pair<int, int>
#define pl pair<ll, ll>
#define pld pair<ld, ld>
#define vpi vector<pii>
#define vpl vector<pl>
#define vpld vector<pld>
#define vmi vector<mint>
#define pmi pair<mint, mint>
 
template<class T> bool ckmin(T &a, const T &b) { return (b < a ? a = b, 1 : 0); }
template<class T> bool ckmax(T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
 
#define dbg(var) { cerr << #var << ": " << var << "\n"; }
 
template<class T, class U> istream& operator>>(istream& in, pair<T, U> &x) { in >> x.fi >> x.se; return in; }
template<class T> istream& operator>>(istream& in, vector<T> &v) { for (auto &x : v) in >> x; return in; }
 
template<class T, class U> ostream& operator<<(ostream& out, const pair<T, U> &x) { out << "(" << x.fi << ", " << x.se << ")"; return out; }
template<class T> ostream& operator<<(ostream& out, const vector<T> &v) { FOR(i,0,sz(v)) out << v[i] << " \n"[i == sz(v) - 1]; return out; }
 
inline namespace FileIO {
  void setIn(str s) { freopen(s.c_str(), "r", stdin); }
	void setOut(str s) { freopen(s.c_str(), "w", stdout); }
	void setIO(str s = "") {
		cin.tie(0)->sync_with_stdio(0);
		if (sz(s)) setIn(s+".in"), setOut(s+".out");
	}
}

struct mint {
  int v; explicit operator int() const { return v; }
  mint(): v(0) {}
  mint(ll _v) {
    v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
    if (v < 0) v += MOD;
  }
  bool operator==(const mint& o) const { return v == o.v; }
	friend bool operator!=(const mint& a, const mint& b) { return !(a == b); }
	friend bool operator<(const mint& a, const mint& b) { return a.v < b.v; }

	mint& operator+=(const mint& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; }
	mint& operator-=(const mint& o) { if ((v -= o.v) < 0) v += MOD; return *this; }
	mint& operator*=(const mint& o) { v = int((ll)v * o.v % MOD); return *this; }
	mint& operator/=(const mint& o) { return (*this) *= inv(o); }
	mint& operator^=(const mint& o) { return (*this) = pow(v, o.v); }
	
	mint& operator+=(const int& o) { if ((v += mint(o).v) >= MOD) v -= MOD; return *this; }
	mint& operator-=(const int& o) { if ((v -= mint(o).v) < 0) v += MOD; return *this; }
	mint& operator*=(const int& o) { v = int((ll)v * mint(o).v % MOD); return *this; }
	mint& operator/=(const int& o) { return (*this) *= inv(mint(o)); }
	mint& operator^=(const int& o) { return (*this) = pow(v, o); }
	
	friend mint pow(mint a, ll p) {
		mint ans = 1; assert(p >= 0);
		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
		return ans;
  }
	friend mint inv(const mint& a) { assert(a.v != 0); return pow(a,MOD-2); }

	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this += 1; }
	mint& operator--() { return *this -= 1; }
	
  friend mint operator+(mint a, const mint& b) { return a += b; }
	friend mint operator-(mint a, const mint& b) { return a -= b; }
	friend mint operator*(mint a, const mint& b) { return a *= b; }
	friend mint operator/(mint a, const mint& b) { return a /= b; }
	friend mint operator^(mint a, const mint& b) { return a ^= b; }
	
	friend mint operator+(mint a, const int& b) { return a += mint(b); }
	friend mint operator-(mint a, const int& b) { return a -= mint(b); }
	friend mint operator*(mint a, const int& b) { return a *= mint(b); }
	friend mint operator/(mint a, const int& b) { return a /= mint(b); }
	friend mint operator^(mint a, const int& b) { return a ^= mint(b); }

	friend istream& operator>>(istream& in, mint& mi) { in >> mi.v; return in; }
	friend ostream& operator<<(ostream& os, const mint& mi) { os << mi.v; return os; }
};

int main() {
  setIO();

	int n, m; cin >> n >> m;
	vs g(n); cin >> g;
	deque<pii> q;
	q.push_back({0, 0});
	vvi d(n, vi(m));
	d[0][0] = 1;
	int ans = 0;
	while (sz(q)) {
		int ci = q.front().fi, cj = q.front().se;
		q.pop_front();
		ckmax(ans, d[ci][cj]);
		FOR(ind,0,4) {
			int x = ci + dx[ind], y = cj + dy[ind];
			if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '.' && d[x][y] == 0) {
				if (g[x][y] == g[ci][cj]) {
					d[x][y] = d[ci][cj];
					q.push_front({x, y});
				} else {
					d[x][y] = d[ci][cj] + 1;
					q.push_back({x, y});
				}
			}
		}
	}
	cout << ans << "\n";

  return 0;
}

Compilation message

tracks.cpp: In function 'void FileIO::setIn(std::string)':
tracks.cpp:68:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   void setIn(str s) { freopen(s.c_str(), "r", stdin); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp: In function 'void FileIO::setOut(std::string)':
tracks.cpp:69:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  void setOut(str s) { freopen(s.c_str(), "w", stdout); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1720 KB	Output is correct
2	Correct	0 ms	308 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	5 ms	1420 KB	Output is correct
5	Correct	2 ms	832 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	2 ms	696 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	4 ms	836 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	696 KB	Output is correct
15	Correct	7 ms	1732 KB	Output is correct
16	Correct	9 ms	1740 KB	Output is correct
17	Correct	6 ms	1740 KB	Output is correct
18	Correct	5 ms	1484 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	700 KB	Output is correct
2	Correct	28 ms	9568 KB	Output is correct
3	Correct	157 ms	96476 KB	Output is correct
4	Correct	45 ms	22704 KB	Output is correct
5	Correct	127 ms	54248 KB	Output is correct
6	Correct	495 ms	110724 KB	Output is correct
7	Correct	1 ms	712 KB	Output is correct
8	Correct	1 ms	696 KB	Output is correct
9	Correct	1 ms	588 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	1 ms	716 KB	Output is correct
12	Correct	1 ms	460 KB	Output is correct
13	Correct	29 ms	9588 KB	Output is correct
14	Correct	17 ms	5684 KB	Output is correct
15	Correct	12 ms	6212 KB	Output is correct
16	Correct	16 ms	4292 KB	Output is correct
17	Correct	76 ms	24504 KB	Output is correct
18	Correct	50 ms	24224 KB	Output is correct
19	Correct	45 ms	22596 KB	Output is correct
20	Correct	37 ms	20808 KB	Output is correct
21	Correct	91 ms	56132 KB	Output is correct
22	Correct	126 ms	54336 KB	Output is correct
23	Correct	166 ms	46744 KB	Output is correct
24	Correct	101 ms	54640 KB	Output is correct
25	Correct	292 ms	96452 KB	Output is correct
26	Correct	289 ms	123944 KB	Output is correct
27	Correct	382 ms	109992 KB	Output is correct
28	Correct	488 ms	110792 KB	Output is correct
29	Correct	485 ms	109132 KB	Output is correct
30	Correct	441 ms	110128 KB	Output is correct
31	Correct	371 ms	62272 KB	Output is correct
32	Correct	333 ms	110988 KB	Output is correct