Submission #466967

#	Time	Username	Problem	Language	Result	Execution time	Memory
466967		mithilshah23	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	687 ms	235896 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#define ll long long
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define vi vector<int>
#define rep(i, n) for (int i = 0; i < n; i++)
#define w(t)  \
    int t;    \
    cin >> t; \
    while (t--)
#define ff first
#define ss second
#define in(azz, sz)                 \
    for (int ix = 0; ix < sz; ix++) \
        cin >> azz[ix];
#define in2d(azz, row, column) rep(i, row) rep(j, column) cin >> azz[i][j];
#define out2d(azz, row, column)                  \
    rep(i, row)                                  \
    {                                            \
        rep(j, column) cout << azz[i][j] << " "; \
        cout << "\n"                             \
    };
#define out(azz, sz)                \
    for (int ix = 0; ix < sz; ix++) \
    {                               \
        cout << azz[ix] << " ";     \
    }                               \
    cout << endl
#define mii map<int, int>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define endl '\n'
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ps(x, y) fixed << setprecision(y) << x
#define mp make_pair
#define all(vx) vx.begin(), vx.end()
#define maxv(azz) max_element(all(azz)) - azz.begin() //return index of max element of vector;
#define minv(azz) min_element(all(azz)) - azz.begin() //return index of min element of vector;
#define maxa(azz) max_element(azz, azz + n) - azz     //return index of max element of array, n==size of array;
#define mina(azz) min_element(azz, azz + n) - azz     //return index of min element of array, n==size of array;
#define isort(azz) is_sorted(all(azz))                //check if elements are sorted;
#define setpres cout.precision(numeric_limits<double>::max_digits10);
#define rev(vx) reverse(all(vx))
#define fastio                    \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef set<int> seti;
#define am(a, b) MOD(MOD(a) + MOD(b))
#define mm(a, b) MOD(MOD(a) * MOD(b))
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
const ll INF = 1000000007;
ll MOD(ll a)
{
    a = a % INF;
    while (a < 0)
        a += INF;
    return a;
}

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = mm(res, a);
        a = mm(a, a);
        b >>= 1;
    }
    return res;
}
ll modInverse(ll a)
{
    return binpow(a, INF - 2);
}
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                                DON'T MAKE CHANGES BEFORE THIS LINE!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
#define int ll //use only if needed;
int depth[5000][5000];
int n = 4000, m = 4000;
int ans = -1;
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
string snow[4000];
bool inside(int x, int y)
{
    return (x > -1 && x < n && y > -1 && y < m && snow[x][y] != '.');
}

void tosolve()
{
    cin >> n >> m;
    rep(i, n) cin >> snow[i];
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    depth[0][0] = 1;

    while (q.size())
    {
        pair<int, int> c = q.front();
        q.pop_front();
        ans = max(ans, depth[c.first][c.second]);

        for (int i = 0; i < 4; i++)
        {
            int x = c.first + dx[i], y = c.second + dy[i];
            if (inside(x, y) && depth[x][y] == 0)
            {
                if (snow[x][y] == snow[c.first][c.second])
                {
                    depth[x][y] = depth[c.first][c.second];
                    q.push_front({x, y});
                }
                else
                {
                    depth[x][y] = depth[c.first][c.second] + 1;
                    q.push_back({x, y});
                }
            }
        }
    }
    cout << ans << endl;
    return;
}

int32_t main()
{
    fastio

    {
        tosolve();
    }
    return 0;
}
/*

███╗░░░███╗██╗████████╗██╗░░██╗██╗██╗░░░░░
████╗░████║██║╚══██╔══╝██║░░██║██║██║░░░░░
██╔████╔██║██║░░░██║░░░███████║██║██║░░░░░
██║╚██╔╝██║██║░░░██║░░░██╔══██║██║██║░░░░░
██║░╚═╝░██║██║░░░██║░░░██║░░██║██║███████╗
╚═╝░░░░░╚═╝╚═╝░░░╚═╝░░░╚═╝░░╚═╝╚═╝╚══════╝

 *  Author : mithilshah23
 *  Website : Oj
 *  Problem : track in the snow
 *  Time : 21-08-2021 11:00:52
 *  Lang : GNU C++17
 */

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