oj.uz

Submission #746793

# Submission time Handle Problem Language Result Execution time Memory
746793 2023-05-23T06:09:18 Z Github Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 535 ms 145236 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const int MAXN = 4500;

char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int dX[] = {1, -1, 0, 0};
int dY[] = {0, 0, 1, -1};
int h, w;

int main(){
    speedup
    cin >> h >> w;
    for (int i = 0; i < h; i++){
        string s; cin >> s;
        for (int j = 0; j < w; j++){
            grid[i][j] = s[j];
        }
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    for (int i = 0; i < MAXN; i++){
        for (int j = 0; j < MAXN; j++){
            dist[i][j] = 0;
        }
    }
    dist[0][0] = 1;
    int ans = 1;
    while (!q.empty()){
        pair<int, int> p = q.front(); q.pop_front();
        int x = p.first, y = p.second;
        ans = max(ans, dist[x][y]);
        for (int i = 0; i < 4; i++){
            int nX = x+dX[i], nY = y+dY[i];
            if (nX >= 0 && nX < h && nY >= 0 && nY < w && grid[nX][nY] != '.' && dist[nX][nY] == 0){
                if (grid[nX][nY] == grid[x][y]){
                    dist[nX][nY] = dist[x][y];
                    q.push_front({nX, nY});
                }else{
                    dist[nX][nY] = dist[x][y]+1;
                    q.push_back({nX, nY});
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 81736 KB Output is correct
2 Correct 29 ms 79608 KB Output is correct
3 Correct 28 ms 79712 KB Output is correct
4 Correct 35 ms 81812 KB Output is correct
5 Correct 31 ms 80744 KB Output is correct
6 Correct 29 ms 79628 KB Output is correct
7 Correct 29 ms 79700 KB Output is correct
8 Correct 28 ms 79820 KB Output is correct
9 Correct 29 ms 79916 KB Output is correct
10 Correct 31 ms 80588 KB Output is correct
11 Correct 37 ms 80456 KB Output is correct
12 Correct 35 ms 80756 KB Output is correct
13 Correct 32 ms 80808 KB Output is correct
14 Correct 34 ms 80768 KB Output is correct
15 Correct 40 ms 81808 KB Output is correct
16 Correct 40 ms 81712 KB Output is correct
17 Correct 39 ms 81584 KB Output is correct
18 Correct 36 ms 81888 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94796 KB Output is correct
2 Correct 59 ms 85028 KB Output is correct
3 Correct 187 ms 97236 KB Output is correct
4 Correct 76 ms 87844 KB Output is correct
5 Correct 171 ms 92904 KB Output is correct
6 Correct 520 ms 110888 KB Output is correct
7 Correct 38 ms 95540 KB Output is correct
8 Correct 37 ms 94872 KB Output is correct
9 Correct 30 ms 79564 KB Output is correct
10 Correct 30 ms 79592 KB Output is correct
11 Correct 38 ms 95196 KB Output is correct
12 Correct 35 ms 80168 KB Output is correct
13 Correct 59 ms 85132 KB Output is correct
14 Correct 51 ms 83500 KB Output is correct
15 Correct 44 ms 83888 KB Output is correct
16 Correct 48 ms 81252 KB Output is correct
17 Correct 105 ms 88484 KB Output is correct
18 Correct 83 ms 88328 KB Output is correct
19 Correct 74 ms 87892 KB Output is correct
20 Correct 66 ms 87408 KB Output is correct
21 Correct 119 ms 93264 KB Output is correct
22 Correct 151 ms 92884 KB Output is correct
23 Correct 170 ms 90640 KB Output is correct
24 Correct 118 ms 93328 KB Output is correct
25 Correct 305 ms 97252 KB Output is correct
26 Correct 350 ms 145236 KB Output is correct
27 Correct 401 ms 123780 KB Output is correct
28 Correct 490 ms 111024 KB Output is correct
29 Correct 535 ms 109120 KB Output is correct
30 Correct 456 ms 114664 KB Output is correct
31 Correct 476 ms 94124 KB Output is correct
32 Correct 368 ms 112520 KB Output is correct