Submission #1283256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283256		ionut27	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	695 ms	64244 KiB

tracks

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e{91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e{39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
    os << "{";
    for (auto& x : v) { os << x << ", "; }
    return os << "}";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
    return os << "{" << p.first << ", " << p.second << "}";
}

#define readFast                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============

#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";

const int N = 1e5 + 15;
const int MOD = 1e9 + 7;

int dl[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

int main() {
    read();
    int n, m;

    fin >> n >> m;
    vector<vector<char>> a(n + 2, vector<char>(m + 2, '.'));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            fin >> a[i][j];
        }
    }
    vector<vector<bool>> vis(n + 2, vector<bool>(m + 2, false));
    deque<pair<int, int>> deq;
    vector<char> history;
    deq.push_front({ 1,1 });
    vis[1][1] = 1;
    history.push_back(a[1][1]);

    while (!deq.empty()) {
        int x = deq.front().first;
        int y = deq.front().second;
        deq.pop_front();

        if (a[x][y] != history.back()) {
            history.push_back(a[x][y]);
        }

        for (int i = 0; i < 4; ++i) {
            int new_x = x + dl[i];
            int new_y = y + dc[i];

            if (vis[new_x][new_y]) continue;

            if (a[new_x][new_y] == a[x][y]) {
                deq.push_front({ new_x, new_y });
            } else if (a[new_x][new_y] != '.') {
                deq.push_back({ new_x, new_y });
            }
            vis[new_x][new_y] = 1;
        }
    }
    cout << sz(history) << '\n';

    return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   * test the solution with the given example
   * int overflow, array bounds, matrix bounds
   * special cases (n=1?)
   * do smth instead of nothing and stay organized
   * WRITE STUFF DOWN
   * DON'T GET STUCK ON ONE APPROACH
~Benq~*/

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