oj.uz

Submission #482105

# Submission time Handle Problem Language Result Execution time Memory
482105 2021-10-23T08:32:10 Z nehasane Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 149380 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];
    priority_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.top()), y = get<2>(q.top());
        q.pop();
        if (visited[x][y])
            continue;
        visited[x][y] = true;
        //check up
        if (x > 0 && meadow[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});
            }
        }
        //check down
        if (x < h-1 && meadow[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});
            }
        }
        //check left
        if (y > 0 && meadow[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});
            }
        }
        //check right
        if (y < w-1 && meadow[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});
            }
        }
    }
    cout << ans+ 1 << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 79556 KB Output is correct
2 Correct 39 ms 78600 KB Output is correct
3 Correct 40 ms 78692 KB Output is correct
4 Correct 72 ms 79472 KB Output is correct
5 Correct 44 ms 78808 KB Output is correct
6 Correct 40 ms 78624 KB Output is correct
7 Correct 47 ms 78672 KB Output is correct
8 Correct 42 ms 78788 KB Output is correct
9 Correct 40 ms 78684 KB Output is correct
10 Correct 47 ms 78864 KB Output is correct
11 Correct 49 ms 78816 KB Output is correct
12 Correct 57 ms 78948 KB Output is correct
13 Correct 55 ms 78896 KB Output is correct
14 Correct 47 ms 78828 KB Output is correct
15 Correct 84 ms 79480 KB Output is correct
16 Correct 108 ms 79560 KB Output is correct
17 Correct 70 ms 79352 KB Output is correct
18 Correct 75 ms 79524 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 78712 KB Output is correct
2 Correct 182 ms 82564 KB Output is correct
3 Correct 680 ms 124504 KB Output is correct
4 Correct 239 ms 89380 KB Output is correct
5 Correct 349 ms 98784 KB Output is correct
6 Execution timed out 2086 ms 149264 KB Time limit exceeded
7 Correct 42 ms 78692 KB Output is correct
8 Correct 49 ms 78684 KB Output is correct
9 Correct 45 ms 78828 KB Output is correct
10 Correct 42 ms 78660 KB Output is correct
11 Correct 43 ms 78668 KB Output is correct
12 Correct 40 ms 78668 KB Output is correct
13 Correct 170 ms 82748 KB Output is correct
14 Correct 118 ms 81340 KB Output is correct
15 Correct 78 ms 81544 KB Output is correct
16 Correct 104 ms 80068 KB Output is correct
17 Correct 380 ms 90200 KB Output is correct
18 Correct 184 ms 90200 KB Output is correct
19 Correct 215 ms 89480 KB Output is correct
20 Correct 176 ms 88644 KB Output is correct
21 Correct 411 ms 99492 KB Output is correct
22 Correct 350 ms 98780 KB Output is correct
23 Correct 713 ms 95824 KB Output is correct
24 Correct 313 ms 99316 KB Output is correct
25 Correct 690 ms 124356 KB Output is correct
26 Correct 1677 ms 104088 KB Output is correct
27 Execution timed out 2077 ms 127620 KB Time limit exceeded
28 Execution timed out 2086 ms 149380 KB Time limit exceeded
29 Execution timed out 2080 ms 136884 KB Time limit exceeded
30 Execution timed out 2082 ms 135996 KB Time limit exceeded
31 Execution timed out 2066 ms 101608 KB Time limit exceeded
32 Execution timed out 2080 ms 126272 KB Time limit exceeded