Submission #654542

#	Time	Username	Problem	Language	Result	Execution time	Memory
654542		thinhcute	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	521 ms	115928 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
// ░░░░░░░░░░▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄░░░░░░░░░░░
// ░░░░░░░░▄▀░░░░░░░░░░░░░░▄░░░░░░░▀▄░░░░░░░░░
// ░░░░░░░░█░░▄░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░░░
// ░░░░░░░░█░░░░░░░░░░░░░░░░▄█▄▄░░▄░░░█░▄▄▄░░░
// ░▄▄▄▄▄░░█░░░░░░▀░░░░░░░░▀█░░▀▄░░░░░█▀▀░██░░
// ░██▄▀██▄█░░░▄░░░░░░░░░░░██░░░░▀▀▀▀▀░░░░██░░
// ░░▀██▄▀██░░░░░░░░▀░░░░░██▀░░░░░░░░░░░░░▀██░
// ░░░░▀████░▀░░░░▄░░░░░░░██░░░▄█░░░░▄░▄█░░██░
// ░░░░░░░▀█░░░░▄░░░░░░░░░██░░░░▄░░░▄░░▄░░░██░
// ░░░░░░░▄█▄░░░░░░░░░░░░░░░▀▄░░▀▀▀▀▀▀▀▀░░▄▀░░
// ░░░░░░█▀▀█████████▀▀▀▀▀▀▀▀████████████▀░░░░
// ░░░░░░████▀░░███▀░░░░░░░░░░▀███░░▀██▀░░░░░░
// ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;

// loops
#define FOR(i, a, b) for (int i = (a); i <= (int) (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (int) (b); --i)
#define REP(i, a, b) for (int i = (a); i < (int) (b); ++i)
#define each(a, x) for (auto &a : x)

// pairs
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second

// vectors
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
using vi = V<int>;
using vb = V<bool>;
using vs = V<string>;
using vpi = V<pii>;

#define sz(x) (int) (x).size()
#define len(x) (int) (x).length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back

// others
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, b) memset((a), (b), sizeof(a))

#define lb lower_bound
#define ub upper_bound

// in and out
#define setp(x) fixed << setprecision((int) x)
#define endl '\n'
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << "{ " << p.fi << ", " << p.se << " }"; }
template<class T> ostream &operator<<(ostream &os, const V<T> &v) { os << "{ "; REP(i, 0, sz(v) - 1) os << v[i] << ", "; return os << v[sz(v) - 1] << " }"; }

const int imax = INT_MAX;
const int imin = INT_MIN;
const ll BIG = (ll) 1e18; // not too close to LLONG_MAX
const db PI = acos((db) - 1);
const vi d4x = { -1, 0, 1, 0 }, d4y = { 0, 1, 0, -1 };
const vi d8x = { -1, -1, 0, 1, 1, 1, 0, -1 }, d8y = { 0, 1, 1, 1, 0, -1, -1, -1 };

// SOME USEFULL STUFFS !!!

// bit
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

template<class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // a = min(a,b);
template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } // a = max(a,b);

// sort and remove duplicates
template<class T> void remDup(vector<T> &v) { sort(all(v)); v.erase(unique(all(v)), v.end()); }

// hmm quick power
template<class T> T qpow(T a, ll b, const ll &M = LLONG_MAX) { T r = 1; a %= M; assert(b >= 0); do { if (b & 1) r = (r * a) % M; a = (a * a) % M; } while (b >>= 1); return r; }

// check if N is power of 2
bool ispow2(ll n) { return n && (n & -n) == n; }

void setIO(string NAME = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if ((int) NAME.length() && fopen((NAME + ".inp").c_str(), "r")) {
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }
}

// #define TIMER // <--- enable if you need to know the excution time :333

const int MOD = (int) 1e9 + 7; // 998244353;
const int maxN = (int) 1e5 + 5;

ull modMul(ull a, ull b, ull M) { ll ret = a * b - M * ull(1.L / M * a * b); return ret + M * (ret < 0) - M * (ret >= (ll) M); }
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mul(ll x, ll y) { return modMul(x, y, MOD); }

int n, m;
bool mark[4040][4040];
string s[4040];

bool isValid(int r, int c)
{
    return r >= 0 && c >= 0 && r < n && c < m;
}

void solve()
{
    ms(mark, false);

    cin >> n >> m;
    FOR(i, 0, n - 1) cin >> s[i];

    deque<pair<int, pair<int, int>>> q;
    q.push_front({1, {0, 0}});
    mark[0][0] = true;

    int res = 0;
    while (sz(q)) {
        res += q.front().fi;
        int r = q.front().se.fi, c = q.front().se.se;
        q.pop_front();

        FOR(k, 0, 3) {
            int nr = r + d4x[k], nc = c + d4y[k];
            if (!isValid(nr, nc) || mark[nr][nc] || s[nr][nc] == '.') continue;
            mark[nr][nc] = true;
            if (s[nr][nc] == s[r][c]) q.push_front({0, {nr, nc}});
            else {
                int tr = q.back().se.fi, tc = q.back().se.se;
                if (s[tr][tc] == s[nr][nc]) q.push_back({0, {nr, nc}});
                else q.push_back({1, {nr, nc}});
            }
        }
    }

    cout << res << endl;
}

int main()
{
    #ifdef TIMER
    auto start = chrono::high_resolution_clock::now();
    #endif

    setIO();

    int tc = 1;
    // cin >> tc; // More than 1 testcase?

    while (tc--) {
        solve();
    }

    #ifdef TIMER
    auto stop = chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<chrono::microseconds>(stop - start);
    cout << "Execution time: " << duration.count() << " microseconds" << endl;
    #endif

    return 0;
}

// CODED BY:
//  _____         _   __               _____ _       _   __      _
// |_   _|       | | / /              /  ___(_)     | | / /     | |
//   | | ___ _ __| |/ /  ___ _ __ _ __\ `--. _ _   _| |/ / _   _| |_ ___  ___ 
//   | |/ _ \ '__|    \ / _ \ '__| '__|`--. \ | | | |    \| | | | __/ _ \/ _ \
//   | |  __/ |  | |\  \  __/ |  | |  /\__/ / | |_| | |\  \ |_| | ||  __/  __/
//   \_/\___|_|  \_| \_/\___|_|  |_|  \____/|_|\__,_\_| \_/\__,_|\__\___|\___|

Compilation message (stderr)

tracks.cpp:178:1: warning: multi-line comment [-Wcomment]
  178 | //   | |/ _ \ '__|    \ / _ \ '__| '__|`--. \ | | | |    \| | | | __/ _ \/ _ \
      | ^
tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen((NAME + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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