Submission #710780

#	Time	Username	Problem	Language	Result	Execution time	Memory
710780		pls33	Tracks in the Snow (BOI13_tracks)	C++17	2.19 / 100	663 ms	132856 KiB

tracks

// boi2013 day2 p2
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai
using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;
using f80 = long double;
#pragma endregion

using grid_t = vector<string>;

const vi16 dx = {1, -1, 0, 0};
const vi16 dy = {0, 0, 1, -1};

bool inside(p32 a, int row, int col)
{
    return a.first >= 0 && a.first < row &&
           a.second >= 0 && a.second < col;
}

int main()
{
#ifndef _AAAAAAAAA
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#else
    freopen("tracks.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int row, col;
    cin >> row >> col;

    grid_t grid(row);
    for (auto &r : grid)
    {
        cin >> r;
    }

    vvi32 dist(row, vi32(col, INT_MAX));
    dist[0][0] = 0;
    deque<p32> q;
    q.emplace_back(0, 0);

    int ans = 0;
    while (!q.empty())
    {
        auto [r, c] = q.front();
        q.pop_front();

        for (int i = 0; i < (int)dx.size(); i++)
        {
            int n_r = r + dx[i];
            int n_c = c + dy[i];

            if (!inside({n_r, n_c}, row, col) || dist[n_r][n_c] != INT_MAX)
            {
                continue;
            }

            if (grid[r][c] == grid[n_r][n_c])
            {
                dist[n_r][n_c] = dist[r][c];
                ans = max(ans, dist[n_r][n_c]);
                q.emplace_front(n_r, n_c);
            }
            else
            {
                dist[n_r][n_c] = dist[r][c] + 1;
                ans = max(ans, dist[n_r][n_c]);
                q.emplace_back(n_r, n_c);
            }
        }
    }

    cout << max(ans, 1) << '\n';

    return 0;
}

Compilation message (stderr)

tracks.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
tracks.cpp:33: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   33 | #pragma endregion
      |

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