Submission #1289385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289385		windowwife	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1954 ms	919632 KiB

tracks

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const int maxn = 4005;
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;
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;
        }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j] == '.') continue;
            if (par[i][j].first != 0) continue;
            par[i][j] = {i, j};
            dq.push_back({i, j});
            while (!dq.empty())
            {
                int i = dq.front().first, j = dq.front().second;
                dq.pop_front();
                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] && par[ni][nj].first == 0)
                    {
                        par[ni][nj] = par[i][j];
                        dq.push_back({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])
                {
                    adj[par[i][j].first][par[i][j].second].push_back(par[ni][nj]);
                    adj[par[ni][nj].first][par[ni][nj].second].push_back(par[i][j]);
                }
            }
        }
    dq.push_back(par[m][n]);
    d[par[m][n].first][par[m][n].second] = 1;
    res = 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: 70 / 70