oj.uz

Submission #973456

# Submission time Handle Problem Language Result Execution time Memory
973456 2024-05-02T02:59:43 Z Br3ad Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 681 ms 140856 KB 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)

const int N = 4e3 + 5;
const int M = 1e9 + 7; 
const int INF = 0x3f3f3f3f;

const int xMove[4] = {0, 1, 0, -1};
const int yMove[4] = {1, 0, -1, 0};

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // ifstream cin();
    // ofstream cout();
    
    char meadow[N][N];
    int h, w;
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> meadow[i][j];
        }
    }

    deque<pair<int, int>> q;
    int depth[N][N]{0}, ans = 0;

    q.push_front(MP(0, 0));
    depth[0][0] = 1;

    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop_front();

        ans = max(ans, depth[x][y]);

        for(int i = 0; i < 4; i++){
            int new_x = x + xMove[i];
            int new_y = y + yMove[i];
            if(new_x < 0 || new_x >= h || new_y < 0 || new_y >= w) continue;
            if(meadow[new_x][new_y] == '.') continue;
            if(depth[new_x][new_y] != 0) continue;

            if(meadow[x][y] == meadow[new_x][new_y]){
                depth[new_x][new_y] = depth[x][y];
                q.push_front(MP(new_x, new_y));
            }else {
                depth[new_x][new_y] = depth[x][y] + 1;
                q.push_back(MP(new_x, new_y));
            }
        }
    }

    cout << ans << endl;
    
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 79184 KB Output is correct
2 Correct 42 ms 78840 KB Output is correct
3 Correct 46 ms 78960 KB Output is correct
4 Correct 50 ms 79184 KB Output is correct
5 Correct 44 ms 78932 KB Output is correct
6 Correct 41 ms 78904 KB Output is correct
7 Correct 43 ms 78676 KB Output is correct
8 Correct 42 ms 78912 KB Output is correct
9 Correct 47 ms 78784 KB Output is correct
10 Correct 43 ms 78928 KB Output is correct
11 Correct 43 ms 78928 KB Output is correct
12 Correct 45 ms 78808 KB Output is correct
13 Correct 45 ms 78784 KB Output is correct
14 Correct 43 ms 79000 KB Output is correct
15 Correct 51 ms 78932 KB Output is correct
16 Correct 52 ms 79184 KB Output is correct
17 Correct 48 ms 78928 KB Output is correct
18 Correct 46 ms 79184 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 78932 KB Output is correct
2 Correct 84 ms 80816 KB Output is correct
3 Correct 270 ms 94576 KB Output is correct
4 Correct 108 ms 82480 KB Output is correct
5 Correct 181 ms 87876 KB Output is correct
6 Correct 632 ms 108980 KB Output is correct
7 Correct 48 ms 78952 KB Output is correct
8 Correct 44 ms 78928 KB Output is correct
9 Correct 43 ms 78940 KB Output is correct
10 Correct 43 ms 78900 KB Output is correct
11 Correct 43 ms 78952 KB Output is correct
12 Correct 42 ms 78928 KB Output is correct
13 Correct 97 ms 80720 KB Output is correct
14 Correct 72 ms 79636 KB Output is correct
15 Correct 61 ms 79696 KB Output is correct
16 Correct 60 ms 79700 KB Output is correct
17 Correct 134 ms 82768 KB Output is correct
18 Correct 118 ms 82736 KB Output is correct
19 Correct 106 ms 82516 KB Output is correct
20 Correct 96 ms 82280 KB Output is correct
21 Correct 178 ms 87852 KB Output is correct
22 Correct 168 ms 87524 KB Output is correct
23 Correct 224 ms 86316 KB Output is correct
24 Correct 180 ms 87636 KB Output is correct
25 Correct 432 ms 94500 KB Output is correct
26 Correct 681 ms 140856 KB Output is correct
27 Correct 608 ms 120308 KB Output is correct
28 Correct 632 ms 108812 KB Output is correct
29 Correct 654 ms 106176 KB Output is correct
30 Correct 644 ms 112920 KB Output is correct
31 Correct 424 ms 89432 KB Output is correct
32 Correct 647 ms 118464 KB Output is correct