oj.uz

Submission #372534

# Submission time Handle Problem Language Result Execution time Memory
372534 2021-02-28T17:48:15 Z ml1234 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1066 ms 134632 KB 
#include <iostream>
#include <deque>
using namespace std;
bool check(int x, int y);

int h, w;
string snow[4000];
int main() 
{
    cin >> h >> w;
    for (int i = 0; i < h; i++)
    {
        cin >> snow[i];
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    int depth[h][w];
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            depth[i][j] = 0;
        }
    }
    depth[0][0] = 1;
    int ans = 1;
    int dx[] = {-1, 0, 0, 1}, dy[] = {0, -1, 1, 0};
    while (!q.empty())
    {
        pair<int, int> curr = q.front();
        q.pop_front();
        ans = max(ans, depth[curr.first][curr.second]);
        for (int i = 0; i < 4; i++)
        {
            int x = curr.first + dx[i], y = curr.second + dy[i];
            if (check(x, y) && depth[x][y] == 0)
            {
                if (snow[x][y] == snow[curr.first][curr.second])
                {
                    q.push_front({x, y});
                    depth[x][y] = depth[curr.first][curr.second];
                }
                else
                {
                    q.push_back({x, y});
                    depth[x][y] = depth[curr.first][curr.second] + 1;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

bool check(int x, int y)
{
    return x >= 0 && x < h && y >= 0 && y < w && snow[x][y] != '.';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2156 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 10 ms 1644 KB Output is correct
5 Correct 5 ms 1004 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 4 ms 876 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 7 ms 1004 KB Output is correct
13 Correct 4 ms 1004 KB Output is correct
14 Correct 4 ms 1004 KB Output is correct
15 Correct 16 ms 2156 KB Output is correct
16 Correct 17 ms 2156 KB Output is correct
17 Correct 13 ms 2028 KB Output is correct
18 Correct 10 ms 1644 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 76 ms 10476 KB Output is correct
3 Correct 555 ms 94956 KB Output is correct
4 Correct 145 ms 24940 KB Output is correct
5 Correct 364 ms 49056 KB Output is correct
6 Correct 1064 ms 109536 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 76 ms 10476 KB Output is correct
14 Correct 42 ms 6636 KB Output is correct
15 Correct 39 ms 7148 KB Output is correct
16 Correct 34 ms 4332 KB Output is correct
17 Correct 203 ms 26348 KB Output is correct
18 Correct 166 ms 26220 KB Output is correct
19 Correct 145 ms 24684 KB Output is correct
20 Correct 126 ms 23040 KB Output is correct
21 Correct 324 ms 50028 KB Output is correct
22 Correct 361 ms 48492 KB Output is correct
23 Correct 385 ms 42348 KB Output is correct
24 Correct 324 ms 49260 KB Output is correct
25 Correct 786 ms 94188 KB Output is correct
26 Correct 666 ms 112508 KB Output is correct
27 Correct 931 ms 134632 KB Output is correct
28 Correct 1066 ms 108904 KB Output is correct
29 Correct 1061 ms 105844 KB Output is correct
30 Correct 993 ms 109036 KB Output is correct
31 Correct 776 ms 53356 KB Output is correct
32 Correct 854 ms 116392 KB Output is correct