oj.uz

Submission #366821

# Submission time Handle Problem Language Result Execution time Memory
366821 2021-02-15T10:34:45 Z ngpin04 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 653 ms 119164 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 4e3 + 5;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

char a[N][N];

int dis[N][N];
int n,m,ans;

void bfs(int i, int j)
{
    deque <pair <int, int>> q;

    q.push_back(mp(i, j));
    dis[i][j] = 1;

    while (q.size())
    {
        pair <int, int> cur = q.front();
        q.pop_front();
        int x = cur.fi;
        int y = cur.se;

        for (int dir = 0; dir < 4; dir++)
        {
            int u = x + dx[dir];
            int v = y + dy[dir];
            if (min(u, v) > 0 && u <= n && v <= m && dis[u][v] == 0 && a[u][v] != '.')
            {
                if (a[u][v] == a[x][y])
                {
                    q.push_front(mp(u, v));
                    dis[u][v] = dis[x][y];
                } else {
                    q.push_back(mp(u, v));
                    dis[u][v] = dis[x][y] + 1;
                }
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j - 1];
    }

    bfs(n, m);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        ans = max(ans, dis[i][j]);

    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5228 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 9 ms 5100 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 3 ms 2412 KB Output is correct
11 Correct 3 ms 2156 KB Output is correct
12 Correct 6 ms 3052 KB Output is correct
13 Correct 4 ms 2924 KB Output is correct
14 Correct 3 ms 2924 KB Output is correct
15 Correct 12 ms 5100 KB Output is correct
16 Correct 17 ms 5228 KB Output is correct
17 Correct 11 ms 5244 KB Output is correct
18 Correct 9 ms 5100 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 30956 KB Output is correct
2 Correct 49 ms 13548 KB Output is correct
3 Correct 247 ms 57800 KB Output is correct
4 Correct 80 ms 29164 KB Output is correct
5 Correct 183 ms 44652 KB Output is correct
6 Correct 653 ms 91384 KB Output is correct
7 Correct 21 ms 32236 KB Output is correct
8 Correct 20 ms 30828 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 22 ms 31596 KB Output is correct
12 Correct 2 ms 1644 KB Output is correct
13 Correct 49 ms 13548 KB Output is correct
14 Correct 28 ms 9580 KB Output is correct
15 Correct 30 ms 12268 KB Output is correct
16 Correct 20 ms 5100 KB Output is correct
17 Correct 123 ms 24944 KB Output is correct
18 Correct 119 ms 31880 KB Output is correct
19 Correct 80 ms 29164 KB Output is correct
20 Correct 58 ms 22352 KB Output is correct
21 Correct 138 ms 43500 KB Output is correct
22 Correct 190 ms 44652 KB Output is correct
23 Correct 236 ms 36296 KB Output is correct
24 Correct 146 ms 40940 KB Output is correct
25 Correct 489 ms 78828 KB Output is correct
26 Correct 367 ms 119164 KB Output is correct
27 Correct 527 ms 113256 KB Output is correct
28 Correct 620 ms 91256 KB Output is correct
29 Correct 619 ms 91104 KB Output is correct
30 Correct 568 ms 96368 KB Output is correct
31 Correct 546 ms 63596 KB Output is correct
32 Correct 448 ms 101032 KB Output is correct