oj.uz

Submission #1000998

# Submission time Handle Problem Language Result Execution time Memory
1000998 2024-06-18T12:28:04 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
80.2083 / 100
 463 ms 120580 KB 
#include <bits/stdc++.h>
using i64 = long long;

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int h, w;
    std::cin >> h >> w;
    
    std::vector<std::string> g(h);
    for (auto &s : g) {
        std::cin >> s;
    }

    std::vector dis(h, std::vector<int>(w));
    std::vector vis(h, std::vector<bool>(w));
    dis[0][0] = 0;

    std::deque<std::tuple<int, int>> q;
    q.push_back({0, 0});
    vis[0][0] = true;

    int ans = 0;
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop_front();

        ans = std::max(ans, dis[x][y]);
        
        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (tx < 0 || tx >= h || ty < 0 || ty >= w || g[x][y] == '.' || vis[tx][ty]) {
                continue;
            }
            
            if (g[x][y] == g[tx][ty]) {
                dis[tx][ty] = dis[x][y];
                q.push_front({tx, ty});
            } else {
                dis[tx][ty] = dis[x][y] + 1;
                q.push_back({tx, ty});
            }
            vis[tx][ty] = true;
        }
    }
    std::cout << ans << "\n";

    return 0;
}

Subtask #1
23.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1884 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 6 ms 1628 KB Output isn't correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Incorrect 1 ms 604 KB Output isn't correct
12 Correct 3 ms 856 KB Output is correct
13 Correct 2 ms 1008 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 8 ms 2076 KB Output is correct
16 Correct 8 ms 1884 KB Output is correct
17 Correct 10 ms 1884 KB Output is correct
18 Incorrect 5 ms 1624 KB Output isn't correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 48 ms 9376 KB Output is correct
3 Correct 220 ms 91516 KB Output is correct
4 Correct 63 ms 21844 KB Output is correct
5 Correct 166 ms 51284 KB Output is correct
6 Incorrect 447 ms 105920 KB Output isn't correct
7 Correct 3 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 37 ms 9564 KB Output is correct
14 Correct 20 ms 5720 KB Output is correct
15 Correct 18 ms 6236 KB Output is correct
16 Correct 16 ms 4104 KB Output is correct
17 Correct 103 ms 23644 KB Output is correct
18 Correct 73 ms 23384 KB Output is correct
19 Correct 59 ms 21852 KB Output is correct
20 Correct 51 ms 20056 KB Output is correct
21 Correct 133 ms 53332 KB Output is correct
22 Correct 166 ms 51280 KB Output is correct
23 Correct 209 ms 44368 KB Output is correct
24 Correct 169 ms 51796 KB Output is correct
25 Correct 361 ms 91276 KB Output is correct
26 Incorrect 241 ms 119840 KB Output isn't correct
27 Incorrect 401 ms 120580 KB Output isn't correct
28 Incorrect 463 ms 105996 KB Output isn't correct
29 Incorrect 450 ms 93616 KB Output isn't correct
30 Incorrect 413 ms 101260 KB Output isn't correct
31 Correct 376 ms 53540 KB Output is correct
32 Correct 370 ms 102928 KB Output is correct