Submission #1011152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011152		i_liek_cheezits	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	375 ms	139876 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double; // or double if tight TL
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define mp make_pair
#define f first
#define s second
#define tcT template<class T
tcT> using V = vector<T>; 
tcT, size_t SZ> using AR = array<T,SZ>;
using vi = V<int>;
using vl = V<ll>;
using vb = V<bool>;
using vpii = V<pii>;
using vpll = V<pll>;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rz resize
#define pb push_back
#define ft front()
#define bk back()
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const ll INF = 2e18;
const db PI = acos((db)-1);
mt19937 rng(0); // or mt19937_64
tcT> bool ckmin(T& a, const T& b) {
	return b < a ? a = b, 1 : 0; } // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0; } // set a = max(a,b)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAX_N = 4e3; 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int depth[MAX_N][MAX_N];
char grid[MAX_N][MAX_N];
int main() {
  fastIO
  F0R(i, MAX_N) memset(depth[i], 0, sizeof(depth[i]));
    int n, m; cin >> n >> m;
    F0R(i, n) {
        string s; cin >> s;
        F0R(j, m) {
            grid[i][j] = s[j];
        }
    }
    auto inrange = [&](pii p) ->bool{
       return p.f >= 0 && p.f < n && p.s >= 0 && p.s < m && grid[p.f][p.s] != '.';
    };
    deque<pii> q; int ans = 0;
    q.push_front({0, 0}); depth[0][0] = 1;
    while(!q.empty()) {
        pii p = q.ft; 
        q.pop_front();
        ckmax(ans, depth[p.f][p.s]);
        F0R(i, 4) {
            pii np = {p.f + dx[i], p.s + dy[i]};
            if (inrange(np) && depth[np.f][np.s] == 0) {
                if (grid[p.f][p.s] == grid[np.f][np.s]) {
                    depth[np.f][np.s] = depth[p.f][p.s];
                    q.push_front(np);
                } else {
                    depth[np.f][np.s] = depth[p.f][p.s] + 1;
                    q.pb(np);
                }
            } 
        }
    }
    cout << ans << '\n';
}

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