oj.uz

Submission #959003

# Submission time Handle Problem Language Result Execution time Memory
959003 2024-04-07T11:15:15 Z DaoMinh Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 613 ms 93324 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] != '.')
            {
                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);
                }
                a[v.x][v.y] = '.';
            }
        }
    }
    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 13148 KB Output isn't correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Incorrect 1 ms 4700 KB Output isn't correct
4 Incorrect 5 ms 12892 KB Output isn't correct
5 Incorrect 3 ms 8920 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 2 ms 6608 KB Output isn't correct
9 Incorrect 1 ms 6748 KB Output isn't correct
10 Incorrect 2 ms 8796 KB Output isn't correct
11 Incorrect 2 ms 8796 KB Output isn't correct
12 Incorrect 3 ms 8920 KB Output isn't correct
13 Incorrect 2 ms 8920 KB Output isn't correct
14 Incorrect 3 ms 8792 KB Output isn't correct
15 Incorrect 6 ms 13148 KB Output isn't correct
16 Incorrect 7 ms 13168 KB Output isn't correct
17 Incorrect 6 ms 13400 KB Output isn't correct
18 Incorrect 5 ms 12888 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 76376 KB Output isn't correct
2 Incorrect 27 ms 30812 KB Output isn't correct
3 Incorrect 209 ms 92980 KB Output isn't correct
4 Incorrect 64 ms 43092 KB Output isn't correct
5 Incorrect 140 ms 70224 KB Output isn't correct
6 Incorrect 566 ms 93136 KB Output isn't correct
7 Incorrect 10 ms 78616 KB Output isn't correct
8 Incorrect 10 ms 76380 KB Output isn't correct
9 Incorrect 1 ms 2396 KB Output isn't correct
10 Incorrect 1 ms 2396 KB Output isn't correct
11 Incorrect 10 ms 78532 KB Output isn't correct
12 Incorrect 2 ms 6756 KB Output isn't correct
13 Incorrect 28 ms 30804 KB Output isn't correct
14 Incorrect 17 ms 21852 KB Output isn't correct
15 Incorrect 21 ms 24192 KB Output isn't correct
16 Incorrect 12 ms 11356 KB Output isn't correct
17 Incorrect 70 ms 45396 KB Output isn't correct
18 Incorrect 63 ms 45496 KB Output isn't correct
19 Incorrect 54 ms 43128 KB Output isn't correct
20 Incorrect 58 ms 40916 KB Output isn't correct
21 Incorrect 127 ms 72576 KB Output isn't correct
22 Incorrect 149 ms 70228 KB Output isn't correct
23 Incorrect 129 ms 58848 KB Output isn't correct
24 Incorrect 124 ms 72272 KB Output isn't correct
25 Incorrect 307 ms 93028 KB Output isn't correct
26 Incorrect 444 ms 83172 KB Output isn't correct
27 Incorrect 577 ms 92904 KB Output isn't correct
28 Incorrect 613 ms 93060 KB Output isn't correct
29 Incorrect 575 ms 93008 KB Output isn't correct
30 Incorrect 556 ms 92244 KB Output isn't correct
31 Incorrect 365 ms 75500 KB Output isn't correct
32 Incorrect 491 ms 93324 KB Output isn't correct