Submission #1276130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276130		voidptr	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	647 ms	212764 KiB

tracks

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define mod 1000000007
#define mod2 998244353

using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

bool inside(ll y, ll x, ll n, ll m)
{
    return (y < n && y >= 0 && x < m && x >= 0);
}

void solve()
{
    ll n, m;
    cin >> n >> m;

    vector<string> a(n);

    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    vector<vector<ll>> dist(n, vector<ll>(m, -1));
    vector<ll> yMove = {1, 0, -1, 0};
    vector<ll> xMove = {0, 1, 0, -1};

    dist[0][0] = 1;

    deque<pair<ll, ll>> dq;
    dq.push_front({0, 0});
    while(!dq.empty())
    {
        auto [y, x] = dq.front(); dq.pop_front();

        for(int i = 0; i < 4; ++i)
        {
            ll newY = y + yMove[i];
            ll newX = x + xMove[i];
            if(inside(newY, newX, n, m))
            {
                if(dist[newY][newX] != -1 || a[newY][newX] == '.') continue;
                if(a[y][x] != a[newY][newX])
                {
                    dist[newY][newX] = dist[y][x] + 1;
                    dq.push_back({newY, newX});
                }else 
                {
                    dist[newY][newX] = dist[y][x];
                    dq.push_front({newY, newX});
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < m; ++j)
        {
            ans = max(ans, dist[i][j]);
            // cout << dist[i][j] << " ";
        }
        // cout << "\n";
    }

    cout << ans << "\n";
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    solve();
}

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