Submission #1156097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156097		zyadhany	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1732 ms	306332 KiB

tracks

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<ll>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}

const int MODE = 998244353;

using namespace std;

vp dl = {{0,1}, {0,-1}, {1, 0}, {-1, 0}};

void solve(int tc) {
    ll n, m;

    cin >> n >> m;

    vcc X(n + 10, vc(m + 10, '.'));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> X[i+1][j+1];

    ll at = 1;
    vii ord(n + 10, vi(m + 10));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (X[i][j] == '.' || ord[i][j]) continue;
            stack<pl> st;
            st.push({i, j});
            ord[i][j] = at;
            while (!st.empty()) {
                auto [l, r] = st.top();
                st.pop();
                
                for (auto [x, y] : dl) {
                    ll a = l + x;
                    ll b = r + y;
                    if (!ord[a][b] && X[a][b] == X[i][j]) {
                        ord[a][b] = at;
                        st.push({a, b});
                    }
                }
            }
            at++;
        }
    }
        
    ll res = 1;
    deque<pl> que;
    vii vis(n + 10, vi(m + 10, INT32_MAX));
    vis[1][1] = 1;
    que.push_front({1, 1});
    while (!que.empty())
    {
        pl p = que.front();
        que.pop_front();

        for (auto [x, y] : dl) {
            ll a = x + p.first;
            ll b = y + p.second;
            ll w = (ord[a][b] != ord[p.first][p.second]);
            if (X[a][b] != '.' && vis[a][b] > w + vis[p.first][p.second]) {
                vis[a][b] = w + vis[p.first][p.second];
                if (w) que.push_back({a,b});
                else que.push_front({a,b});
                res = max(res, vis[a][b]);
            }
        }
    }
    
    cout << res << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;

    // freopen("piggyback.in", "r", stdin);
    // freopen("piggyback.out", "w", stdout);

    // cin >> size;
    for (int i = 1; i <= size; i++)
        solve(i);
}

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