Submission #692458

#	Time	Username	Problem	Language	Result	Execution time	Memory
692458		lovezah	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	612 ms	131028 KiB

tracks

/*{{{*/
#include <bits/stdc++.h>
//namespace newbiezah {
#ifdef LOCAL
#include "E:\cp-Library\debug.h"
#else
#define dbg(...)
#endif

#define ALL(x) (x).begin(), (x).end() 
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int((x).size()))
#define REV(x) reverse(ALL(x))
#define UNIQUE(x) sort(ALL(x)), x.erase(unique(ALL(x)), x.end())
#define msk(x) (1 << (x))
#define rsz resize
#define fi first
#define se second
#define ft front()
#define bk back()
#define ppb pop_back()
#define ppf pop_front()
#define pb push_back
#define pf push_front
#define eb emplace_back 
#define mp make_pair
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define tcT template<class T

tcT> using V = std::vector<T>;
tcT> int ilb(V<T> &a, const T &b) { return int(lb(ALL(a), b) - a.begin()); }
tcT> int iub(V<T> &a, const T &b) { return int(ub(ALL(a), b) - a.begin()); }
tcT, size_t sz> using AR = std::array<T, sz>;
using ll = int64_t;
using db = double;
using str = std::string;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using VI = V<int>;
using VL = V<ll>;
using VS = V<str>;
using VB = V<bool>;
using VPI = V<pi>;
using VPL = V<pl>;

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

tcT> using pq = std::priority_queue<T>;
tcT> using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
tcT> bool ckmax(T &u, T v) { return v > u ? u = v, true : false; }
tcT> bool ckmin(T &u, T v) { return v < u ? u = v, true : false; }

#define FOR(i, a, n) for (int i = (a); i < (n); i++)
#define F0R(i, n) FOR(i, 0, n)
#define FORd(i, a, n) for (int i = (n) - 1; i >= (a); i--)
#define F0Rd(i, n) FORd(i, 0, n)
#define rep(n) F0R(_, n)
#define trav(a, v) for (auto &a : v)
#define each(a, b, v) for (auto &&[a, b] : v)
#define each3(a, b, c, v) for (auto &&[a, b, c] : v)

const char nl = '\n';
const int mod1 = int(1e9)+7, mod9 = 998244353;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
//} // namespace newbiezah
//using namespace newbiezah;
using namespace std;
/*}}}*/

const int N = 4010;
str g[N];
int n, m, d[N][N], ans;

bool valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '.' && !d[x][y];
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;
    F0R(i, n) cin >> g[i];
    deque<pi> q; q.pb({0, 0});
    d[0][0] = 1;
    while (!q.empty()) {
        auto [x, y] = q.ft; q.ppf;
        ckmax(ans, d[x][y]);
        F0R(i, 4) {
            int nx = x+dx[i], ny = y+dy[i];
            if (valid(nx, ny)) {
                if (g[nx][ny] == g[x][y]) {
                    d[nx][ny] = d[x][y];
                    q.pf({nx, ny});
                } else {
                    d[nx][ny] = d[x][y]+1;
                    q.pb({nx, ny});
                }
            }
        }
    }
    cout << ans << nl;
    return 0;
}

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