Submission #1227459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227459		fucio	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	2136 ms	1114112 KiB

tracks

// https://oj.uz/problem/view/BOI13_tracks

#include <bits/stdc++.h>

using namespace std;

#define DEBUG 0

#if DEBUG
#define HAS_EXTRA 1
#include "./codeforces/debug.hpp"
#endif

typedef long long int ll;
typedef vector<int> vint;
typedef vector<ll> vlong;

#define loop(a, b) for (int i = a; i < b; i++)
#define loop0(a) for (int i = 0; i < a; i++)
#define all(x) x.begin(), x.end()
#define contains(v, x) (find(begin(v), end(v), x) != end(v))

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    for (int i = 0; i < v.size(); ++i)
    {
        os << v[i];
        if (i != v.size() - 1)
            os << " ";
    }
    return os;
}
inline void printV(const vector<pair<int, int>> &v)
{
    for (auto &[x, y] : v)
        cout << '(' << x << ',' << y << ") ";
    cout << '\n';
}

vector<vector<char>> readGrid()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> res(n, vector<char>(m, 'a'));
    loop0(n) for (int j = 0; j < m; j++)
            cin >>
        res[i][j];
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<vector<char>> g = readGrid();
    vector<vint> moves = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int c = 0;
    vector<pair<int, int>> pos = {make_pair(0, 0)};
    while (!pos.empty())
    {
        // printV(pos);
        vector<pair<int, int>> p(pos.begin(), pos.end());
        vector<pair<int, int>> newpos;
        pos.clear();
        char curr = g[p[0].first][p[0].second];
        // cout << curr << endl;
        // BFS from p
        while (!p.empty())
        {
            vector<pair<int, int>> np;
            for (auto pr : p)
            {
                loop0(4)
                {
                    int x = pr.first + moves[i][0];
                    int y = pr.second + moves[i][1];
                    if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size())
                        continue;
                    char val = g[x][y];
                    if (val != curr && val != '.')
                    {
                        g[x][y] = '.';
                        newpos.push_back(make_pair(x, y));
                    }
                    if (val == curr)
                    {
                        g[x][y] = '.';
                        np.push_back(make_pair(x, y));
                    }
                }
            }

            p.swap(np);
        }
        pos.swap(newpos);
        c++;
    }
    cout << c;
    return 0;
}

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