Submission #1242767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242767		erlandmb	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1304 ms	212900 KiB

tracks

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG
#endif
#include <iostream>
#include <tuple>
#include <set>
#include <map>
#include <bitset>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <cstdint>
#include <chrono>
#include <thread>
#include <omp.h>
#include <iomanip>
#include <numeric>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
 
#define fastIO                   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pb                       push_back
#define mp                       make_pair
#define f                        first
#define s                        second
#define sz(a)                    (int)a.size()
#define all(a)                   (a).begin(), (a).end()
#define mem(a, h)		         memset(a, (h), sizeof(a))
#define forn(i, n)			     for (int i = 0; i < n; i++)
#define fore(i, b, e)	         for (int i = b; i < e; i++)
#define forev(i, e, b)           for (int i = e; i > b; i--)
#define dbg(x)                   cerr<<#x<<" = "<<(x)<<endl
#define UNIQUE(x)                (x).resize(unique(all(x)) - (x).begin())
#define RAYA                     cout<<"=============================="<<'\n'
#define yes                      cout << "YES" << endl;
#define no                       cout << "NO" << endl;
#define PI                       acos(-1)
#define chmax(x, y)              x = max(x, y)
#define chmin(x, y)              x = min(x, y) 
#define next_p(v)                next_permutation(v.begin(),v.end())

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &x : a) in >> x;
    return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &a) {
    for (auto &x : a) out << x << " ";
    return out;
}

using ll = long long;
using ld = long double;

template <typename T> using vc = vector<T>;
template <typename T> using vv = vc<vc<T>>;
using vl = vc<ll>; using vvl = vv<ll>;
using vs = vc<string>; using vvs = vv<string>;
using vld = vc<ld>; using vvld = vv<ld>;
using pl = pair<ll, ll>;
using ar2 = array<ll, 2>;
using ar3 = array<ll, 3>;

template <typename T> 
using pq = priority_queue<T, vc<T>>;
template <typename T> 
using pq_g = priority_queue<T, vc<T>, greater<T>>;


const int MOD = 998244353;
const ll INF = ll(2e18);
const int inf = int(1e9);

// modint template 
struct mint {
	int v;
	explicit operator int() const { return v; }
	mint() { v = 0; }
	mint(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mint &operator+=(mint &a, mint b) {
	if ((a.v += b.v) >= MOD) a.v -= MOD;
	return a;
}
mint &operator-=(mint &a, mint b) {
	if ((a.v -= b.v) < 0) a.v += MOD;
	return a;
}
mint operator+(mint a, mint b) { return a += b; }
mint operator-(mint a, mint b) { return a -= b; }
mint operator*(mint a, mint b) { return mint((long long)a.v * b.v); }
mint &operator*=(mint &a, mint b) { return a = a * b; }
mint pow(mint a, long long p) {
	assert(p >= 0);
	return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mint inv(mint a) {
	assert(a.v != 0);
	return pow(a, MOD - 2);
}
mint operator/(mint a, mint b) { return a * inv(b); }
//

ll exp(ll x, ll n) { if (n == 0) return 1; ll u = exp(x, n / 2); u = (u * u); if (n % 2 == 1) u = (u * x); return u; }

ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}
 
ll lcm(ll a, ll b) {return (a * b) / gcd(a, b);}
//
vl dx = {1, 0, -1, 0}; //vl dx = {1, 1, 0, -1, -1, -1, 0, 1};
vl dy = {0, 1, 0, -1}; //vl dy = {0, 1, 1, 1, 0, -1, -1, -1};
    
bool inside(ll i, ll j, ll h, ll w) {
    return (0 <= i && i < h && 0 <= j && j < w);
}
//

void solve() {
    ll n, m; cin >> n >> m;
    vc<string> grid(n);
    forn (i, n) cin >> grid[i];
    deque<ar2> q;
    vvl dist(n, vl(m, 0));
    q.push_front({0, 0});
    dist[0][0] = 1;
    ll ans = 0;
    while (sz(q)) {
        auto [x, y] = q.front(); q.pop_front();
        chmax(ans, dist[x][y]);
        forn (k, 4) {
            ll nx = x + dx[k], ny = y + dy[k];
            if (!inside(nx, ny, n, m) || dist[nx][ny] != 0 || grid[nx][ny] == '.') continue;
            if (grid[nx][ny] == grid[x][y]) {
                dist[nx][ny] = dist[x][y];
                q.push_front({nx, ny});
            } else {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
    }
    cout << ans << '\n';
}


int main() {
    fastIO;
    // cout << fixed;
    // cout << setprecision(10);
    // neighbors.assign(n, vll());
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

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