Submission #1289377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289377		windowwife	Tracks in the Snow (BOI13_tracks)	C++20	36.56 / 100	94 ms	47156 KiB

tracks

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 1001, mod = 998244353;
int m, n, di[4] = {0, 0, 1, -1}, dj[4] = {1, -1, 0, 0}, sz[maxn][maxn], d[maxn][maxn], res = 0;
pair<int, int> par[maxn][maxn];
vector<pair<int, int>> adj[maxn][maxn];
char c[maxn][maxn];
deque<pair<int, int>> dq;
pair<int, int> find_set (int i, int j)
{
    if (par[i][j].first == i && par[i][j].second == j) return {i, j};
    return (par[i][j] = find_set(par[i][j].first, par[i][j].second));
}
void union_set (int i, int j, int u, int v)
{
    pair<int, int> p1 = find_set(i, j);
    pair<int, int> p2 = find_set(u, v);
    if (p1.first == p2.first && p1.second == p2.second) return;
    if (sz[p1.first][p1.second] < sz[p2.first][p2.second])
    {
        swap(p1.first, p2.first);
        swap(p1.second, p2.second);
    }
    par[p2.first][p2.second] = {p1.first, p1.second};
    sz[p1.first][p1.second] += sz[p2.first][p2.second];
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(d, -1, sizeof(d));
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> c[i][j];
            sz[i][j] = 1;
            par[i][j] = {i, j};
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j] == '.') continue;
            for (int d = 0; d < 4; d++)
            {
                int ni = i + di[d], nj = j + dj[d];
                if (ni < 1 || ni > m || nj < 1 || nj > n) continue;
                if (c[i][j] == c[ni][nj]) union_set(i, j, ni, nj);
            }
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j] == '.') continue;
            for (int d = 0; d < 4; d++)
            {
                int ni = i + di[d], nj = j + dj[d];
                if (ni < 1 || ni > m || nj < 1 || nj > n) continue;
                if (c[ni][nj] == '.') continue;
                if (c[i][j] != c[ni][nj])
                {
                    //cout << find_set(i, j).first << " " << find_set(i, j).second << " " << find_set(ni, nj).first << " " << find_set(ni, nj).second << '\n';
                    adj[find_set(i, j).first][find_set(i, j).second].push_back(find_set(ni, nj));
                    adj[find_set(ni, nj).first][find_set(ni, nj).second].push_back(find_set(i, j));
                }
            }
        }
    dq.push_back(find_set(m, n));
    d[find_set(m, n).first][find_set(m, n).second] = 1;
    while (!dq.empty())
    {
        int x = dq.front().first, y = dq.front().second;
        dq.pop_front();
        for (pair<int, int> p : adj[x][y])
            if (d[p.first][p.second] == -1)
            {
                d[p.first][p.second] = d[x][y] + 1;
                res = max(res, d[p.first][p.second]);
                dq.push_back(p);
            }
    }
    cout << res;
}

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