oj.uz

Submission #366818

# Submission time Handle Problem Language Result Execution time Memory
366818 2021-02-15T10:32:30 Z ngpin04 Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 1093 ms 128784 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] = 0;

    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)
            {
                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];
    }

    memset(dis, -1, sizeof(dis));

    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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 65388 KB Output isn't correct
2 Incorrect 33 ms 63212 KB Output isn't correct
3 Incorrect 34 ms 63340 KB Output isn't correct
4 Incorrect 39 ms 65388 KB Output isn't correct
5 Incorrect 36 ms 64364 KB Output isn't correct
6 Incorrect 34 ms 63212 KB Output isn't correct
7 Incorrect 39 ms 63468 KB Output isn't correct
8 Incorrect 33 ms 63340 KB Output isn't correct
9 Incorrect 35 ms 63596 KB Output isn't correct
10 Incorrect 36 ms 64364 KB Output isn't correct
11 Incorrect 35 ms 64108 KB Output isn't correct
12 Incorrect 42 ms 64492 KB Output isn't correct
13 Incorrect 37 ms 64364 KB Output isn't correct
14 Incorrect 37 ms 64492 KB Output isn't correct
15 Incorrect 43 ms 65644 KB Output isn't correct
16 Incorrect 44 ms 65388 KB Output isn't correct
17 Incorrect 43 ms 65260 KB Output isn't correct
18 Incorrect 41 ms 65388 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 78188 KB Output isn't correct
2 Incorrect 90 ms 72684 KB Output isn't correct
3 Incorrect 490 ms 118596 KB Output isn't correct
4 Incorrect 180 ms 72812 KB Output isn't correct
5 Incorrect 300 ms 113520 KB Output isn't correct
6 Incorrect 687 ms 93192 KB Output isn't correct
7 Incorrect 43 ms 78956 KB Output isn't correct
8 Incorrect 42 ms 78188 KB Output isn't correct
9 Incorrect 35 ms 63340 KB Output isn't correct
10 Incorrect 34 ms 63340 KB Output isn't correct
11 Incorrect 50 ms 78700 KB Output isn't correct
12 Incorrect 35 ms 64000 KB Output isn't correct
13 Incorrect 84 ms 72684 KB Output isn't correct
14 Incorrect 63 ms 69740 KB Output isn't correct
15 Incorrect 84 ms 70508 KB Output isn't correct
16 Incorrect 54 ms 66796 KB Output isn't correct
17 Incorrect 174 ms 82176 KB Output isn't correct
18 Incorrect 273 ms 81656 KB Output isn't correct
19 Incorrect 169 ms 72940 KB Output isn't correct
20 Incorrect 160 ms 80576 KB Output isn't correct
21 Incorrect 314 ms 98352 KB Output isn't correct
22 Incorrect 308 ms 113792 KB Output isn't correct
23 Incorrect 276 ms 92972 KB Output isn't correct
24 Incorrect 300 ms 102040 KB Output isn't correct
25 Incorrect 1093 ms 118484 KB Output isn't correct
26 Incorrect 369 ms 128784 KB Output isn't correct
27 Incorrect 498 ms 114920 KB Output isn't correct
28 Incorrect 621 ms 92912 KB Output isn't correct
29 Incorrect 617 ms 92384 KB Output isn't correct
30 Incorrect 574 ms 98928 KB Output isn't correct
31 Incorrect 544 ms 77548 KB Output isn't correct
32 Incorrect 520 ms 104744 KB Output isn't correct