oj.uz

Submission #730922

# Submission time Handle Problem Language Result Execution time Memory
730922 2023-04-26T15:44:44 Z sleepntsheep Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 668 ms 166628 KB 
#include <bits/stdc++.h>
using namespace std;

#define N 5005
char a[N][N]; int n, m, z, d[N][N], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
deque<pair<int, int>> q;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    memset(d, 63, sizeof d);
    q.emplace_back(1, 1); d[1][1] = 1;
    while (q.size())
    {
        auto [y, x] = q.front(); q.pop_front();
        z = max(z, d[y][x]);
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (!a[ny][nx] || a[ny][nx] == '.') continue;
            if (a[ny][nx] == a[y][x] && d[ny][nx] > d[y][x])
            {
                d[ny][nx] = d[y][x];
                q.emplace_front(ny, nx);
            }
            if (a[ny][nx] != a[y][x] && d[ny][nx] > d[y][x] + 1)
            {
                d[ny][nx] = d[y][x] + 1;
                q.emplace_back(ny, nx);
            }
        }
    }

    printf("%d", z);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
tracks.cpp:11:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
      |                                  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 100772 KB Output is correct
2 Correct 38 ms 98332 KB Output is correct
3 Correct 37 ms 98516 KB Output is correct
4 Correct 46 ms 100752 KB Output is correct
5 Correct 40 ms 99560 KB Output is correct
6 Correct 37 ms 98352 KB Output is correct
7 Correct 37 ms 98432 KB Output is correct
8 Correct 38 ms 98560 KB Output is correct
9 Correct 39 ms 98680 KB Output is correct
10 Correct 43 ms 99404 KB Output is correct
11 Correct 47 ms 99260 KB Output is correct
12 Correct 44 ms 99692 KB Output is correct
13 Correct 41 ms 99732 KB Output is correct
14 Correct 42 ms 99664 KB Output is correct
15 Correct 48 ms 100852 KB Output is correct
16 Correct 51 ms 100764 KB Output is correct
17 Correct 48 ms 100676 KB Output is correct
18 Correct 45 ms 100760 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 113740 KB Output is correct
2 Correct 80 ms 105240 KB Output is correct
3 Correct 244 ms 119012 KB Output is correct
4 Correct 94 ms 108304 KB Output is correct
5 Correct 145 ms 114128 KB Output is correct
6 Correct 662 ms 132372 KB Output is correct
7 Correct 43 ms 114424 KB Output is correct
8 Correct 46 ms 113700 KB Output is correct
9 Correct 39 ms 98500 KB Output is correct
10 Correct 40 ms 98356 KB Output is correct
11 Correct 44 ms 114064 KB Output is correct
12 Correct 38 ms 98856 KB Output is correct
13 Correct 82 ms 105236 KB Output is correct
14 Correct 63 ms 103480 KB Output is correct
15 Correct 55 ms 103984 KB Output is correct
16 Correct 62 ms 100876 KB Output is correct
17 Correct 148 ms 109028 KB Output is correct
18 Correct 100 ms 108852 KB Output is correct
19 Correct 96 ms 108456 KB Output is correct
20 Correct 87 ms 107692 KB Output is correct
21 Correct 151 ms 114448 KB Output is correct
22 Correct 146 ms 114048 KB Output is correct
23 Correct 234 ms 111564 KB Output is correct
24 Correct 142 ms 114540 KB Output is correct
25 Correct 370 ms 118944 KB Output is correct
26 Correct 668 ms 166628 KB Output is correct
27 Correct 564 ms 137268 KB Output is correct
28 Correct 662 ms 132280 KB Output is correct
29 Correct 638 ms 129868 KB Output is correct
30 Correct 633 ms 135892 KB Output is correct
31 Correct 601 ms 115452 KB Output is correct
32 Correct 607 ms 135780 KB Output is correct