oj.uz

Submission #959061

# Submission time Handle Problem Language Result Execution time Memory
959061 2024-04-07T12:50:14 Z DaoMinh Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 599 ms 130308 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] != '.' && deg[v.x][v.y] == 0)
            {
                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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7512 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 6 ms 7256 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 3 ms 5468 KB Output is correct
11 Correct 3 ms 5468 KB Output is correct
12 Correct 5 ms 5980 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 9 ms 7256 KB Output is correct
16 Correct 10 ms 7516 KB Output is correct
17 Correct 8 ms 7356 KB Output is correct
18 Correct 6 ms 7512 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32348 KB Output is correct
2 Correct 38 ms 18252 KB Output is correct
3 Correct 252 ms 70528 KB Output is correct
4 Correct 78 ms 34636 KB Output is correct
5 Correct 193 ms 53644 KB Output is correct
6 Correct 599 ms 104576 KB Output is correct
7 Correct 12 ms 32860 KB Output is correct
8 Correct 9 ms 32348 KB Output is correct
9 Correct 2 ms 2588 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 14 ms 32748 KB Output is correct
12 Correct 2 ms 5028 KB Output is correct
13 Correct 39 ms 18004 KB Output is correct
14 Correct 21 ms 11196 KB Output is correct
15 Correct 19 ms 15196 KB Output is correct
16 Correct 17 ms 8028 KB Output is correct
17 Correct 100 ms 30160 KB Output is correct
18 Correct 74 ms 36948 KB Output is correct
19 Correct 72 ms 34700 KB Output is correct
20 Correct 57 ms 28468 KB Output is correct
21 Correct 150 ms 52304 KB Output is correct
22 Correct 151 ms 53804 KB Output is correct
23 Correct 190 ms 44240 KB Output is correct
24 Correct 143 ms 49768 KB Output is correct
25 Correct 342 ms 91064 KB Output is correct
26 Correct 326 ms 130308 KB Output is correct
27 Correct 408 ms 117584 KB Output is correct
28 Correct 502 ms 104584 KB Output is correct
29 Correct 517 ms 102976 KB Output is correct
30 Correct 474 ms 107092 KB Output is correct
31 Correct 429 ms 74608 KB Output is correct
32 Correct 364 ms 102808 KB Output is correct