oj.uz

Submission #958994

# Submission time Handle Problem Language Result Execution time Memory
958994 2024-04-07T11:03:15 Z DaoMinh Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 402 ms 160176 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int maxN = 4e3 + 1;   
const int MOD = 1e9 + 7;

struct TCell
{
    int x, y;
};

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, m, deg[maxN][maxN];
char a[maxN][maxN];

void ReadInput()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
}

bool IsOut(const TCell &u)
{
    return u.x < 1 || u.x > n || u.y < 1 || u.y > m;
}

void Solve()
{
    int res = 1;
    deg[1][1] = 1;
    deque<TCell> Q;
    Q.push_front({1, 1});
    while (!Q.empty())
    {
        TCell u = Q.front();
        Q.pop_front();
        res = max(res, deg[u.x][u.y]);
        for (int i = 0; i < 4; i++)
        {
            TCell v = {u.x + dx[i], u.y + dy[i]};
            if (!IsOut(v) && a[v.x][v.y] != '.')
            {
                a[v.x][v.y] = '.';
                if (a[v.x][v.y] == a[u.x][u.y])
                {
                    deg[v.x][v.y] = deg[u.x][u.y];
                    Q.push_front(v);
                }
                else
                {
                    deg[v.x][v.y] = deg[u.x][u.y] + 1;
                    Q.push_back(v);
                }
            }
        }
    }
    cout << res;
}

#define task ""
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    int T = 1;
    //cin >> T;
    while (T--)
    {
        ReadInput();
        Solve();
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13660 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Incorrect 5 ms 13660 KB Output isn't correct
5 Incorrect 2 ms 8796 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 1 ms 4700 KB Output isn't correct
8 Incorrect 1 ms 6748 KB Output isn't correct
9 Incorrect 2 ms 6748 KB Output isn't correct
10 Incorrect 2 ms 8796 KB Output isn't correct
11 Incorrect 3 ms 9052 KB Output isn't correct
12 Incorrect 3 ms 9176 KB Output isn't correct
13 Incorrect 3 ms 9304 KB Output isn't correct
14 Incorrect 3 ms 8796 KB Output isn't correct
15 Incorrect 6 ms 13660 KB Output isn't correct
16 Incorrect 7 ms 13656 KB Output isn't correct
17 Incorrect 7 ms 13248 KB Output isn't correct
18 Incorrect 6 ms 13660 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 76368 KB Output isn't correct
2 Incorrect 26 ms 31984 KB Output isn't correct
3 Incorrect 202 ms 98012 KB Output isn't correct
4 Incorrect 52 ms 43344 KB Output isn't correct
5 Incorrect 135 ms 70736 KB Output isn't correct
6 Incorrect 376 ms 160176 KB Output isn't correct
7 Incorrect 11 ms 78684 KB Output isn't correct
8 Incorrect 10 ms 76548 KB Output isn't correct
9 Incorrect 1 ms 2652 KB Output isn't correct
10 Incorrect 1 ms 2396 KB Output isn't correct
11 Incorrect 10 ms 78424 KB Output isn't correct
12 Incorrect 2 ms 6748 KB Output isn't correct
13 Incorrect 25 ms 32060 KB Output isn't correct
14 Incorrect 16 ms 22620 KB Output isn't correct
15 Incorrect 20 ms 24152 KB Output isn't correct
16 Incorrect 12 ms 12124 KB Output isn't correct
17 Incorrect 66 ms 48204 KB Output isn't correct
18 Incorrect 80 ms 45420 KB Output isn't correct
19 Incorrect 52 ms 43348 KB Output isn't correct
20 Incorrect 45 ms 41708 KB Output isn't correct
21 Incorrect 130 ms 75244 KB Output isn't correct
22 Incorrect 136 ms 70760 KB Output isn't correct
23 Incorrect 116 ms 65172 KB Output isn't correct
24 Incorrect 117 ms 73084 KB Output isn't correct
25 Incorrect 386 ms 94620 KB Output isn't correct
26 Incorrect 286 ms 134368 KB Output isn't correct
27 Incorrect 402 ms 159872 KB Output isn't correct
28 Incorrect 369 ms 159932 KB Output isn't correct
29 Incorrect 393 ms 159748 KB Output isn't correct
30 Incorrect 384 ms 158940 KB Output isn't correct
31 Incorrect 233 ms 107704 KB Output isn't correct
32 Incorrect 337 ms 119452 KB Output isn't correct