oj.uz

Submission #886002

# Submission time Handle Problem Language Result Execution time Memory
886002 2023-12-11T10:29:28 Z noobHeMan Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 408 ms 130940 KB 
#include<bits/stdc++.h>
using namespace std;

#define int         int 
#define double      double

const int INF = INT_MAX-10;
const int NINF = -INF;
const int MOD = 998244353;

int dx[4]{-1, 1, 0, 0}, dy[4]{0, 0, -1, 1};

const int maxH = 4005, maxW = 4005;
string grid[maxH];
int dist[maxH][maxW];

int H, W;
bool inside(int x, int y) {
    return x >= 0 && y >= 0 && x < H && y < W && grid[x][y] != '.'; 
}

int ans = 0;
void solve() {
    cin >> H >> W;

    for(int i=0; i<H; i++) {
        cin >> grid[i];
    }

    deque<pair<int, int>> dq;
    dq.push_back({0,0});
    dist[0][0] = 1;

    while(!dq.empty()) {
        pair<int, int> a = dq.front();
        dq.pop_front();
        
        ans = max(ans, dist[a.first][a.second]);

        for(int i=0; i<4; i++) {
            int x = a.first + dx[i], y = a.second + dy[i];
            if(inside(x, y) && dist[x][y] == 0) {
                if(grid[x][y] == grid[a.first][a.second]) {
                    dist[x][y] = dist[a.first][a.second];
                    dq.push_front({x, y});
                } else {
                    dist[x][y] = dist[a.first][a.second] + 1;
                    dq.push_back({x, y});
                }
            }
        }
    }

    cout << ans << "\n";
}

int32_t main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cout << fixed << setprecision(10);

    int t = 1;
//    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3928 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 5 ms 3672 KB Output is correct
5 Correct 2 ms 2136 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1744 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 3 ms 2140 KB Output is correct
13 Correct 3 ms 2140 KB Output is correct
14 Correct 2 ms 2140 KB Output is correct
15 Correct 8 ms 3788 KB Output is correct
16 Correct 8 ms 3932 KB Output is correct
17 Correct 6 ms 3672 KB Output is correct
18 Correct 5 ms 3676 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15964 KB Output is correct
2 Correct 29 ms 12068 KB Output is correct
3 Correct 144 ms 75660 KB Output is correct
4 Correct 46 ms 29424 KB Output is correct
5 Correct 115 ms 51524 KB Output is correct
6 Correct 408 ms 109708 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 9 ms 15964 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 7 ms 16476 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 26 ms 11860 KB Output is correct
14 Correct 19 ms 7776 KB Output is correct
15 Correct 12 ms 10332 KB Output is correct
16 Correct 13 ms 4928 KB Output is correct
17 Correct 70 ms 25244 KB Output is correct
18 Correct 56 ms 32340 KB Output is correct
19 Correct 47 ms 29352 KB Output is correct
20 Correct 36 ms 22608 KB Output is correct
21 Correct 88 ms 50512 KB Output is correct
22 Correct 116 ms 51540 KB Output is correct
23 Correct 134 ms 42600 KB Output is correct
24 Correct 93 ms 47864 KB Output is correct
25 Correct 327 ms 96336 KB Output is correct
26 Correct 230 ms 130940 KB Output is correct
27 Correct 286 ms 113588 KB Output is correct
28 Correct 400 ms 109428 KB Output is correct
29 Correct 384 ms 109676 KB Output is correct
30 Correct 347 ms 108992 KB Output is correct
31 Correct 360 ms 72024 KB Output is correct
32 Correct 274 ms 110992 KB Output is correct