Submission #953734

# Submission time Handle Problem Language Result Execution time Memory
953734 2024-03-26T15:11:27 Z Kakarot Tracks in the Snow (BOI13_tracks) C++
0 / 100
80 ms 159268 KB
#include <bits/stdc++.h>
#define int int64_t
using namespace std;

void setIO() {
    cin.tie(0)->sync_with_stdio(0);
}

bool inside(int x, int y, int n, int m, vector<string> &grid) {
    return (x > -1 && x < n && y > -1 && y < m && grid[x][y] != '.');
}

void solve() {
    //cout << "zco";
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for(auto &x : grid) cin >> x;
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    vector<vector<int>> depth(n, vector<int>(n, 1e18));
    depth[0][0] = 0;
    vector<int> di { -1, 0, 1, 0} , dj { 0, 1, 0, -1};
    //auto inside = [](int x, int y, int &n, int &m) { return (x > -1 && x < n && y > -1 && y < m); };
    int ans = 1;
    while(!dq.empty()) {
        auto u = dq.front();
        dq.pop_front();
        ans = max(ans, depth[u.first][u.second]);
        for(int i = 0; i < 4; i++) {
            int x = u.first+di[i], y = u.second+dj[i];
            if(inside(x, y, n, m, grid) && (depth[x][y] + (grid[x][y] != grid[u.first][u.second])) < depth[x][y]) {
                depth[x][y] = depth[u.first][u.second] + (grid[u.first][u.second] != grid[x][y]);
                if(grid[u.first][u.second] != grid[x][y]) dq.push_back({x, y});
                else dq.push_front({x, y});
            }
        }
    }
    cout << ans+1;
}

int32_t main() {
    setIO();
    solve();
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 2512 KB Output isn't correct
5 Incorrect 1 ms 1116 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 1 ms 860 KB Output isn't correct
11 Incorrect 1 ms 856 KB Output isn't correct
12 Incorrect 1 ms 1116 KB Output isn't correct
13 Incorrect 1 ms 1116 KB Output isn't correct
14 Incorrect 1 ms 1116 KB Output isn't correct
15 Incorrect 2 ms 2908 KB Output isn't correct
16 Incorrect 2 ms 2652 KB Output isn't correct
17 Incorrect 1 ms 2648 KB Output isn't correct
18 Incorrect 1 ms 2652 KB Output isn't correct
# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 114700 KB Output isn't correct
2 Incorrect 7 ms 15708 KB Output isn't correct
3 Incorrect 70 ms 159148 KB Output isn't correct
4 Incorrect 17 ms 35924 KB Output isn't correct
5 Incorrect 44 ms 89584 KB Output isn't correct
6 Incorrect 74 ms 159060 KB Output isn't correct
7 Incorrect 44 ms 125780 KB Output isn't correct
8 Incorrect 41 ms 114768 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Incorrect 43 ms 121172 KB Output isn't correct
12 Incorrect 1 ms 600 KB Output isn't correct
13 Incorrect 7 ms 15748 KB Output isn't correct
14 Incorrect 4 ms 8796 KB Output isn't correct
15 Incorrect 6 ms 10332 KB Output isn't correct
16 Incorrect 3 ms 2908 KB Output isn't correct
17 Incorrect 18 ms 40532 KB Output isn't correct
18 Incorrect 20 ms 40020 KB Output isn't correct
19 Incorrect 18 ms 35780 KB Output isn't correct
20 Incorrect 14 ms 31636 KB Output isn't correct
21 Incorrect 41 ms 95020 KB Output isn't correct
22 Incorrect 37 ms 89444 KB Output isn't correct
23 Incorrect 31 ms 65360 KB Output isn't correct
24 Incorrect 40 ms 95288 KB Output isn't correct
25 Incorrect 72 ms 159096 KB Output isn't correct
26 Incorrect 51 ms 121920 KB Output isn't correct
27 Incorrect 71 ms 159056 KB Output isn't correct
28 Incorrect 71 ms 159268 KB Output isn't correct
29 Incorrect 80 ms 159056 KB Output isn't correct
30 Incorrect 68 ms 153440 KB Output isn't correct
31 Incorrect 42 ms 101912 KB Output isn't correct
32 Incorrect 69 ms 159240 KB Output isn't correct