Submission #596493

# Submission time Handle Problem Language Result Execution time Memory
596493 2022-07-14T19:22:05 Z Pratik8696 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
1008 ms 342612 KB
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
// use less_equal to make it multiset
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> p32;
typedef pair<ll, ll> p64;
typedef pair<double, double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int>> vv32;
typedef vector<vector<ll>> vv64;
typedef vector<vector<p64>> vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
typedef vector<pair<p64, ll>> vpp64;
typedef set<ll> s64;
typedef set<p64> sp64;
typedef multiset<ll> ms64;
typedef multiset<p64> msp64;
typedef map<ll, ll> m64;
typedef map<ll, v64> mv64;
typedef unordered_map<ll, v64> uv64;
typedef unordered_map<ll, ll> u64;
typedef unordered_map<p64, ll> up64;
typedef unordered_map<ll, vp64> uvp64;
typedef priority_queue<ll> pq64;
typedef priority_queue<ll, v64, greater<ll>> pqs64;
const int MOD = 1000000007;
double eps = 1e-12;
#define forn(i, n) for (ll i = 0; i < n; i++)
#define forsn(i, s, e) for (ll i = s; i < e; i++)
#define rforn(i, s) for (ll i = s; i >= 0; i--)
#define rforsn(i, s, e) for (ll i = s; i >= e; i--)
struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(p64 x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM) ^ splitmix64(x.second + FIXED_RANDOM);
    }
    size_t operator()(ll x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
typedef gp_hash_table<ll, ll, custom_hash> fm64;
typedef gp_hash_table<p64, ll, custom_hash> fmp64;

#define ln "\n"
#define mp make_pair
#define ie insert
#define pb push_back
#define fi first
#define se second
#define INF 2e18
#define fast_cin()                    \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define al(arr, n) arr, arr + n
#define sz(x) ((ll)(x).size())
#define dbg(a) cout << a << endl;
#define dbg2(a) cout << a << ' ';
using ld = long double;
using db = double;
using str = string; // yay python!
// INPUT
#define tcT template <class T
#define tcTU tcT, class U
#define tcTUU tcT, class... U
tcT > void re(T &x)
{
    cin >> x;
}
tcTUU > void re(T &t, U &...u)
{
    re(t);
    re(u...);
}

int find_set(int v, v64 &parent)
{
    if (-1 == parent[v])
        return v;
    return parent[v] = find_set(parent[v], parent);
}

void union_sets(int a, int b, v64 &parent)
{
    a = find_set(a, parent);
    b = find_set(b, parent);
    if (a != b)
        parent[b] = a;
}

// function for prime factorization
vector<pair<ll, ll>> pf(ll n)
{
    vector<pair<ll, ll>> prime;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            int count = 0;
            while (n % i == 0)
            {
                count++;
                n = n / i;
            }
            prime.pb(mp(i, count));
        }
    }
    if (n > 1)
    {
        prime.pb(mp(n, 1));
    }
    return prime;
}

// sum of digits of a number
ll sumofno(ll n)
{
    ll sum = 0;
    while (n != 0)
    {
        sum += n % 10;
        n = n / 10;
    }
    return sum;
}

// modular exponentiation
long long modpow(long long x, long long n, long long p)
{

    if (n == 0)
        return 1 % p;

    ll ans = 1, base = x;
    while (n > 0)
    {
        if (n % 2 == 1)
        {
            ans = (ans * base) % p;
            n--;
        }
        else
        {
            base = (base * base) % p;
            n /= 2;
        }
    }
    if (ans < 0)
        ans = (ans + p) % p;
    return ans;
}

// const int N = 1e6 + 100;
// long long fact[N];
//  initialise the factorial
// void initfact(){
// fact[0] = 1;
// for (int i = 1; i < N; i++)
//{
// fact[i] = (fact[i - 1] * i);
// fact[i] %= MOD;
// }}

// formula for c
// ll C(ll n, ll i)
//{
// ll res = fact[n];
// ll div = fact[n - i] * fact[i];
// div %= MOD;
// div = modpow(div, MOD - 2, MOD);
// return (res * div) % MOD;
// }

long long CW(ll n, ll m)
{
    if (m > n - m)
        m = n - m;
    long long ans = 1;
    for (int i = 0; i < m; i++)
    {
        ans = ans * (n - i) / (i + 1);
    }
    return ans;
}

// function for fast expo
ll fastexpo(ll a, ll b)
{
    if (b == 0)
    {
        return 1;
    }
    if (a == 0)
    {
        return 0;
    }
    ll y = fastexpo(a, b / 2);
    if (b % 2 == 0)
    {
        return y * y;
    }
    else
    {
        return a * y * y;
    }
}

ll popcount(ll n)
{
    ll c = 0;
    for (; n; ++c)
        n &= n - 1;
    return c;
}

ll ce(ll x, ll y)
{
    ll res = x / y;
    if (x % y != 0)
    {
        res++;
    }
    return res;
}

bool pow2(ll x)
{
    ll res = x & (x - 1);
    if (res == 0)
    {
        return true;
    }
    return false;
}

bool isPrime(int x)
{
    for (int d = 2; d * d <= x; d++)
    {
        if (x % d == 0)
            return false;
    }
    return true;
}

int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

bool isvalid(int x, int y)
{
    if (x < 1 || x > n || y < 1 || y > m)
    {
        return false;
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    vector<vector<char>> arr(n + 10, vector<char>(m + 10, '.'));
    vv64 vis(n + 10, v64(m + 10));
    vv64 dist(n + 10, v64(m + 10));
    forsn(i, 1, n + 1)
    {
        forsn(j, 1, m + 1)
        {
            cin >> arr[i][j];
        }
    }
    deque<p64> q;
    q.push_back({1, 1});
    vis[1][1] = 1;
    dist[1][1] = 1;
    ll ans = 0;
    while (!q.empty())
    {
        ll x1 = q.front().first;
        ll y1 = q.front().second;
        ans = max(ans, dist[x1][y1]);
        q.pop_front();
        forn(i, 4)
        {
            ll X = x1 + dx[i];
            ll Y = y1 + dy[i];
            if (isvalid(X, Y) && arr[X][Y] != '.')
            {
                if (vis[X][Y] == 0)
                {
                    vis[X][Y] = 1;
                    if (arr[x1][y1] == arr[X][Y])
                    {
                        dist[X][Y] = dist[x1][y1];
                        q.push_front({X, Y});
                    }
                    else
                    {
                        dist[X][Y] = dist[x1][y1] + 1;
                        q.push_back({X, Y});
                    }
                }
            }
        }
    }
    cout << ans << ln;
}

int main()
{
    fast_cin();
    //#ifndef ONLINE_JUDGE
    //  freopen("revegetate.in", "r", stdin);
    // freopen("revegetate.out", "w", stdout);
    //#endif
    ll t = 1;
    // cin >> t;
    for (int it = 1; it <= t; it++)
    {
        solve();
    }
    return 0;
}

/*
1. Check borderline constraints. Can a variable you are dividing by be 0?
2. Use ll while using bitshifts
3. Do not erase from set while iterating it
4. Initialise everything
5. Read the task carefully, is something unique, sorted, adjacent, guaranteed??
6. DO NOT use if(!mp[x]) if you want to iterate the map later
7. Are you using i in all loops? Are the i's conflicting?
*/
# Verdict Execution time Memory Grader output
1 Correct 14 ms 4904 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 8 ms 3588 KB Output is correct
5 Correct 3 ms 1876 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 3 ms 1492 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 6 ms 2004 KB Output is correct
13 Correct 3 ms 1876 KB Output is correct
14 Correct 4 ms 1876 KB Output is correct
15 Correct 13 ms 4948 KB Output is correct
16 Correct 14 ms 4904 KB Output is correct
17 Correct 10 ms 4744 KB Output is correct
18 Correct 8 ms 3660 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 2132 KB Output is correct
2 Correct 57 ms 28404 KB Output is correct
3 Correct 413 ms 283936 KB Output is correct
4 Correct 118 ms 67184 KB Output is correct
5 Correct 255 ms 160172 KB Output is correct
6 Correct 889 ms 313252 KB Output is correct
7 Correct 3 ms 2132 KB Output is correct
8 Correct 3 ms 2180 KB Output is correct
9 Correct 3 ms 2004 KB Output is correct
10 Correct 2 ms 1492 KB Output is correct
11 Correct 3 ms 2132 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 58 ms 28316 KB Output is correct
14 Correct 32 ms 16600 KB Output is correct
15 Correct 31 ms 18260 KB Output is correct
16 Correct 27 ms 11996 KB Output is correct
17 Correct 154 ms 72624 KB Output is correct
18 Correct 123 ms 71592 KB Output is correct
19 Correct 113 ms 67080 KB Output is correct
20 Correct 96 ms 61720 KB Output is correct
21 Correct 289 ms 165648 KB Output is correct
22 Correct 259 ms 160172 KB Output is correct
23 Correct 383 ms 137912 KB Output is correct
24 Correct 239 ms 161812 KB Output is correct
25 Correct 660 ms 283988 KB Output is correct
26 Correct 707 ms 317876 KB Output is correct
27 Correct 816 ms 342612 KB Output is correct
28 Correct 996 ms 313248 KB Output is correct
29 Correct 1008 ms 305164 KB Output is correct
30 Correct 1008 ms 317772 KB Output is correct
31 Correct 761 ms 183152 KB Output is correct
32 Correct 737 ms 323100 KB Output is correct