oj.uz

Submission #482110

# Submission time Handle Problem Language Result Execution time Memory
482110 2021-10-23T08:38:14 Z nehasane Tracks in the Snow (BOI13_tracks) C++14
31.7708 / 100
 1014 ms 109132 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAX_H = 4000;
const int MAX_W = 4000;
vector <string> meadow(MAX_H);
bool diff_animal(int x, int y, int diffx, int diffy){
    if (meadow[x][y] != meadow[x + diffx][y + diffy])
        return true;
    return false;
}
int main()
{
    int h, w;
    cin >> h >> w;
    for (int i = 0; i < h; i++)
        cin >> meadow[i];
    queue <tuple <int, int, int>> q;
    int dis[MAX_H][MAX_W];
    bool visited[MAX_H][MAX_W];
    for (int i = 0; i < MAX_H; i++){
        for (int j = 0; j < MAX_W; j++){
            dis[i][j] = INT_MAX;
            visited[i][j] = false;
        }
    }
    q.push({0, 0, 0});
    dis[0][0] = 0;
    int ans = 0;
    while (!q.empty()){
        int x = get<1>(q.front()), y = get<2>(q.front());
        q.pop();
        //check up
        if (x > 0 && meadow[x-1][y] != '.' && !visited[x-1][y]){
            int d = diff_animal(x, y, -1, 0);
            if (dis[x-1][y] > dis[x][y] + d){
                dis[x-1][y] = dis[x][y] + d;
                ans = max(ans, dis[x-1][y]);
                q.push({-dis[x-1][y], x-1, y});
                visited[x-1][y] = true;
            }
        }
        //check down
        if (x < h-1 && meadow[x+1][y] != '.' && !visited[x+1][y]){
            int d = diff_animal(x, y, 1, 0);
            if (dis[x+1][y] > dis[x][y] + d){
                dis[x+1][y] = dis[x][y] + d;
                ans = max(ans, dis[x+1][y]);
                q.push({-dis[x+1][y], x+1, y});
                visited[x+1][y] = true;
            }
        }
        //check left
        if (y > 0 && meadow[x][y-1] != '.' && !visited[x][y-1]){
            int d = diff_animal(x, y, 0, -1);
            if (dis[x][y-1] > dis[x][y] + d){
                dis[x][y-1] = dis[x][y] + d;
                ans = max(ans, dis[x][y-1]);
                q.push({-dis[x][y-1], x, y-1});
                visited[x][y-1] = true;
            }
        }
        //check right
        if (y < w-1 && meadow[x][y+1] != '.' && !visited[x][y+1]){
            int d = diff_animal(x, y, 0, 1);
            if (dis[x][y+1] > dis[x][y] + d){
                dis[x][y+1] = dis[x][y] + d;
                ans = max(ans, dis[x][y+1]);
                q.push({-dis[x][y+1], x, y+1});
                visited[x][y+1] = true;
            }
        }
    }
    cout << ans+ 1 << '\n';
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 79052 KB Output isn't correct
2 Correct 39 ms 78560 KB Output is correct
3 Incorrect 40 ms 78696 KB Output isn't correct
4 Incorrect 48 ms 78864 KB Output isn't correct
5 Incorrect 42 ms 78732 KB Output isn't correct
6 Correct 43 ms 78648 KB Output is correct
7 Incorrect 39 ms 78692 KB Output isn't correct
8 Incorrect 39 ms 78676 KB Output isn't correct
9 Incorrect 42 ms 78684 KB Output isn't correct
10 Incorrect 42 ms 78692 KB Output isn't correct
11 Incorrect 41 ms 78668 KB Output isn't correct
12 Incorrect 43 ms 78812 KB Output isn't correct
13 Incorrect 43 ms 78820 KB Output isn't correct
14 Incorrect 43 ms 78704 KB Output isn't correct
15 Incorrect 51 ms 79108 KB Output isn't correct
16 Incorrect 53 ms 79044 KB Output isn't correct
17 Incorrect 50 ms 79048 KB Output isn't correct
18 Incorrect 46 ms 78896 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 78688 KB Output is correct
2 Incorrect 88 ms 80996 KB Output isn't correct
3 Incorrect 437 ms 108836 KB Output isn't correct
4 Incorrect 146 ms 85700 KB Output isn't correct
5 Correct 302 ms 89992 KB Output is correct
6 Incorrect 946 ms 109132 KB Output isn't correct
7 Correct 42 ms 78668 KB Output is correct
8 Correct 43 ms 78720 KB Output is correct
9 Incorrect 42 ms 78660 KB Output isn't correct
10 Correct 41 ms 78736 KB Output is correct
11 Correct 41 ms 78684 KB Output is correct
12 Correct 40 ms 78668 KB Output is correct
13 Incorrect 88 ms 80992 KB Output isn't correct
14 Incorrect 68 ms 80396 KB Output isn't correct
15 Correct 68 ms 80452 KB Output is correct
16 Incorrect 63 ms 79424 KB Output isn't correct
17 Incorrect 175 ms 86208 KB Output isn't correct
18 Correct 147 ms 86272 KB Output is correct
19 Incorrect 147 ms 85700 KB Output isn't correct
20 Incorrect 130 ms 85176 KB Output isn't correct
21 Incorrect 265 ms 90308 KB Output isn't correct
22 Correct 301 ms 89900 KB Output is correct
23 Incorrect 312 ms 88200 KB Output isn't correct
24 Correct 265 ms 90356 KB Output is correct
25 Correct 556 ms 108904 KB Output is correct
26 Correct 745 ms 91928 KB Output is correct
27 Incorrect 972 ms 108720 KB Output isn't correct
28 Incorrect 1014 ms 108956 KB Output isn't correct
29 Incorrect 999 ms 108952 KB Output isn't correct
30 Incorrect 950 ms 108240 KB Output isn't correct
31 Incorrect 655 ms 91008 KB Output isn't correct
32 Incorrect 969 ms 108968 KB Output isn't correct