Submission #1289490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289490		cpismylifeOwO	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1610 ms	588736 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 4e3 + 5;

int h, w, n;
char arr[MaxN][MaxN];

void Inp()
{
    cin >> h >> w;
    for (int x = 1; x <= h; x++)
    {
        for (int y = 1; y <= w; y++)
        {
            cin >> arr[x][y];
        }
    }
    n = h * w;
}

int Hash(int a, int b)
{
    return (a - 1) * w + b;
}

int parents[MaxN * MaxN];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int FindSet(int p)
{
    if (parents[p] == p)
    {
        return p;
    }
    parents[p] = FindSet(parents[p]);
    return parents[p];
}

void UnionSet(int a, int b)
{
    a = FindSet(a);
    b = FindSet(b);
    if (a == b)
    {
        return;
    }
    parents[b] = a;
}

bool CheckX(int a)
{
    return 1 <= a && a <= h;
}

bool CheckY(int a)
{
    return 1 <= a && a <= w;
}

vector<int> graph[MaxN * MaxN];
queue<int> dq;
int F[MaxN * MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        parents[x] = x;
    }
    for (int x = 1; x <= h; x++)
    {
        for (int y = 1; y <= w; y++)
        {
            if (arr[x][y] == '.')
            {
                continue;
            }
            for (int z = 0; z < 4; z++)
            {
                int newx = x + dx[z], newy = y + dy[z];
                if (CheckX(newx) && CheckY(newy) && arr[newx][newy] == arr[x][y])
                {
                    UnionSet(Hash(newx, newy), Hash(x, y));
                }
            }
        }
    }
    for (int x = 1; x <= h; x++)
    {
        for (int y = 1; y <= w; y++)
        {
            if (arr[x][y] == '.')
            {
                continue;
            }
            for (int z = 0; z < 4; z++)
            {
                int newx = x + dx[z], newy = y + dy[z];
                if (CheckX(newx) && CheckY(newy) && arr[newx][newy] != '.' && arr[newx][newy] != arr[x][y])
                {
                    graph[FindSet(Hash(newx, newy))].push_back(FindSet(Hash(x, y)));
                }
            }
        }
    }
    dq.push(FindSet(1));
    F[FindSet(1)] = 1;
    int res = 0;
    while (!dq.empty())
    {
        int u = dq.front();
        dq.pop();
        res = max(res, F[u]);
        for (int v : graph[u])
        {
            if (!F[v])
            {
                F[v] = F[u] + 1;
                dq.push(v);
            }
        }
    }
    cout << res;
}

int main()
{
    //freopen("B.INP", "r", stdin);
    //freopen("B.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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