oj.uz

Submission #482134

# Submission time Handle Problem Language Result Execution time Memory
482134 2021-10-23T10:40:29 Z nehasane Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 736 ms 127068 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_H = 4000;
const int MAX_W = 4000;

vector <string> meadow(MAX_H);
int dis[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool diff_animal(int x, int y, int diffx, int diffy){
    if (meadow[x][y] != meadow[x + diffx][y + diffy])
        return true;
    return false;
}
bool valid_sq(int x, int y, int h, int w){
    if (x >= 0 && x < h && y >= 0 && y < w && meadow[x][y] != '.')
        return true;
    return false;
}

int main()
{
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> meadow[i];
    deque <pair <int, int>> q;
    memset(dis, -1, sizeof(dis));
    int ans = 0;
    dis[0][0] = 0;
    q.push_back({0, 0});
    while (!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        ans = max(ans, dis[x][y]);
        for (int i = 0; i < 4; i++){
            int curr_x = x + dx[i], curr_y = y + dy[i];
            if (valid_sq(curr_x, curr_y, h, w) && dis[curr_x][curr_y] == -1){
                int d = diff_animal(x, y, dx[i], dy[i]);
                dis[curr_x][curr_y] = dis[x][y] + d;
                if (d == 0)
                    q.push_front({curr_x, curr_y});
                else
                    q.push_back({curr_x, curr_y});
            }
        }
    }
    cout << ans + 1 << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63692 KB Output is correct
2 Correct 22 ms 63052 KB Output is correct
3 Correct 23 ms 63000 KB Output is correct
4 Correct 28 ms 63628 KB Output is correct
5 Correct 25 ms 63232 KB Output is correct
6 Correct 22 ms 62976 KB Output is correct
7 Correct 22 ms 63024 KB Output is correct
8 Correct 22 ms 63052 KB Output is correct
9 Correct 23 ms 63044 KB Output is correct
10 Correct 24 ms 63180 KB Output is correct
11 Correct 23 ms 63172 KB Output is correct
12 Correct 26 ms 63180 KB Output is correct
13 Correct 25 ms 63180 KB Output is correct
14 Correct 25 ms 63180 KB Output is correct
15 Correct 33 ms 63684 KB Output is correct
16 Correct 35 ms 63784 KB Output is correct
17 Correct 32 ms 63692 KB Output is correct
18 Correct 28 ms 63620 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 63052 KB Output is correct
2 Correct 76 ms 65916 KB Output is correct
3 Correct 445 ms 93760 KB Output is correct
4 Correct 131 ms 70596 KB Output is correct
5 Correct 288 ms 74784 KB Output is correct
6 Correct 736 ms 106908 KB Output is correct
7 Correct 24 ms 63016 KB Output is correct
8 Correct 25 ms 63000 KB Output is correct
9 Correct 25 ms 63196 KB Output is correct
10 Correct 26 ms 63100 KB Output is correct
11 Correct 26 ms 63060 KB Output is correct
12 Correct 23 ms 63044 KB Output is correct
13 Correct 81 ms 65852 KB Output is correct
14 Correct 53 ms 65280 KB Output is correct
15 Correct 52 ms 65340 KB Output is correct
16 Correct 47 ms 64324 KB Output is correct
17 Correct 168 ms 71224 KB Output is correct
18 Correct 137 ms 71096 KB Output is correct
19 Correct 128 ms 70568 KB Output is correct
20 Correct 115 ms 70132 KB Output is correct
21 Correct 266 ms 75332 KB Output is correct
22 Correct 284 ms 74820 KB Output is correct
23 Correct 306 ms 72964 KB Output is correct
24 Correct 286 ms 75336 KB Output is correct
25 Correct 541 ms 93604 KB Output is correct
26 Correct 473 ms 127068 KB Output is correct
27 Correct 635 ms 111168 KB Output is correct
28 Correct 730 ms 106972 KB Output is correct
29 Correct 719 ms 107192 KB Output is correct
30 Correct 668 ms 107592 KB Output is correct
31 Correct 539 ms 76092 KB Output is correct
32 Correct 586 ms 109184 KB Output is correct