oj.uz

Submission #482112

# Submission time Handle Problem Language Result Execution time Memory
482112 2021-10-23T08:46:18 Z nehasane Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 792 ms 166080 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];
    deque <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_back({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_front();
        //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]);
                if (d == 0)
                    q.push_front({-dis[x-1][y], x-1, y});
                else
                    q.push_back({-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]);
                if (d == 0)
                    q.push_front({-dis[x+1][y], x+1, y});
                else
                    q.push_back({-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]);
                if (d == 0)
                    q.push_front({-dis[x][y-1], x, y-1});
                else
                    q.push_back({-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]);
                if (d == 0)
                    q.push_front({-dis[x][y+1], x, y+1});
                else
                    q.push_back({-dis[x][y+1], x, y+1});
                visited[x][y+1] = true;
            }
        }
    }
    cout << ans+ 1 << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 79172 KB Output is correct
2 Correct 42 ms 78676 KB Output is correct
3 Correct 40 ms 78612 KB Output is correct
4 Correct 50 ms 79168 KB Output is correct
5 Correct 50 ms 78708 KB Output is correct
6 Correct 39 ms 78644 KB Output is correct
7 Correct 39 ms 78668 KB Output is correct
8 Correct 42 ms 78680 KB Output is correct
9 Correct 40 ms 78660 KB Output is correct
10 Correct 42 ms 78716 KB Output is correct
11 Correct 51 ms 78784 KB Output is correct
12 Correct 44 ms 78768 KB Output is correct
13 Correct 43 ms 78792 KB Output is correct
14 Correct 45 ms 78800 KB Output is correct
15 Correct 51 ms 79104 KB Output is correct
16 Correct 52 ms 79108 KB Output is correct
17 Correct 54 ms 79112 KB Output is correct
18 Correct 47 ms 79172 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 78572 KB Output is correct
2 Correct 92 ms 80968 KB Output is correct
3 Correct 463 ms 108808 KB Output is correct
4 Correct 149 ms 85700 KB Output is correct
5 Correct 303 ms 90140 KB Output is correct
6 Correct 792 ms 128368 KB Output is correct
7 Correct 48 ms 78588 KB Output is correct
8 Correct 43 ms 78668 KB Output is correct
9 Correct 42 ms 78800 KB Output is correct
10 Correct 41 ms 78700 KB Output is correct
11 Correct 41 ms 78660 KB Output is correct
12 Correct 39 ms 78668 KB Output is correct
13 Correct 94 ms 81060 KB Output is correct
14 Correct 75 ms 80324 KB Output is correct
15 Correct 85 ms 80528 KB Output is correct
16 Correct 63 ms 79380 KB Output is correct
17 Correct 188 ms 86308 KB Output is correct
18 Correct 153 ms 86212 KB Output is correct
19 Correct 157 ms 85700 KB Output is correct
20 Correct 134 ms 85292 KB Output is correct
21 Correct 303 ms 90376 KB Output is correct
22 Correct 294 ms 90136 KB Output is correct
23 Correct 322 ms 88096 KB Output is correct
24 Correct 281 ms 90344 KB Output is correct
25 Correct 539 ms 108796 KB Output is correct
26 Correct 574 ms 166080 KB Output is correct
27 Correct 681 ms 134604 KB Output is correct
28 Correct 782 ms 128212 KB Output is correct
29 Correct 785 ms 128600 KB Output is correct
30 Correct 740 ms 129736 KB Output is correct
31 Correct 579 ms 91448 KB Output is correct
32 Correct 666 ms 131664 KB Output is correct