oj.uz

Submission #482109

# Submission time Handle Problem Language Result Execution time Memory
482109 2021-10-23T08:36:24 Z nehasane Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 133604 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();
        //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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 79284 KB Output is correct
2 Correct 41 ms 78680 KB Output is correct
3 Correct 41 ms 78612 KB Output is correct
4 Correct 67 ms 79420 KB Output is correct
5 Correct 42 ms 78812 KB Output is correct
6 Correct 39 ms 78596 KB Output is correct
7 Correct 40 ms 78696 KB Output is correct
8 Correct 41 ms 78668 KB Output is correct
9 Correct 41 ms 78824 KB Output is correct
10 Correct 44 ms 78788 KB Output is correct
11 Correct 46 ms 78800 KB Output is correct
12 Correct 55 ms 78788 KB Output is correct
13 Correct 45 ms 78744 KB Output is correct
14 Correct 48 ms 78812 KB Output is correct
15 Correct 79 ms 79204 KB Output is correct
16 Correct 84 ms 79304 KB Output is correct
17 Correct 62 ms 79172 KB Output is correct
18 Correct 71 ms 79472 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78660 KB Output is correct
2 Correct 166 ms 81120 KB Output is correct
3 Correct 635 ms 108836 KB Output is correct
4 Correct 223 ms 85720 KB Output is correct
5 Correct 370 ms 90044 KB Output is correct
6 Execution timed out 2087 ms 133604 KB Time limit exceeded
7 Correct 42 ms 78600 KB Output is correct
8 Correct 41 ms 78660 KB Output is correct
9 Correct 45 ms 78816 KB Output is correct
10 Correct 40 ms 78668 KB Output is correct
11 Correct 41 ms 78660 KB Output is correct
12 Correct 40 ms 78708 KB Output is correct
13 Correct 175 ms 81128 KB Output is correct
14 Correct 116 ms 80324 KB Output is correct
15 Correct 73 ms 80524 KB Output is correct
16 Correct 100 ms 79480 KB Output is correct
17 Correct 380 ms 86356 KB Output is correct
18 Correct 188 ms 86212 KB Output is correct
19 Correct 211 ms 85812 KB Output is correct
20 Correct 171 ms 85344 KB Output is correct
21 Correct 375 ms 90308 KB Output is correct
22 Correct 318 ms 89952 KB Output is correct
23 Correct 717 ms 88168 KB Output is correct
24 Correct 322 ms 90428 KB Output is correct
25 Correct 759 ms 108868 KB Output is correct
26 Correct 1617 ms 92060 KB Output is correct
27 Execution timed out 2099 ms 112020 KB Time limit exceeded
28 Execution timed out 2091 ms 133508 KB Time limit exceeded
29 Execution timed out 2103 ms 121200 KB Time limit exceeded
30 Execution timed out 2102 ms 120640 KB Time limit exceeded
31 Execution timed out 2103 ms 91588 KB Time limit exceeded
32 Execution timed out 2088 ms 110416 KB Time limit exceeded