oj.uz

Submission #515617

# Submission time Handle Problem Language Result Execution time Memory
515617 2022-01-19T10:47:58 Z KoD Patkice II (COCI21_patkice2) C++17
110 / 110
 263 ms 40900 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int inf = std::numeric_limits<int>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int H, W;
    std::cin >> H >> W;
    vector<char> grid(H * W);
    for (auto& x : grid) {
        std::cin >> x;
    }
    int src = 0, dst = 0;
    while (grid[src] != 'o') src += 1;
    while (grid[dst] != 'x') dst += 1;
    vector<int> dist(H * W, inf), parent(H * W, -1);
    dist[src] = 0;
    std::deque<int> que = {src};
    while (!que.empty()) {
        const int u = que.front();
        que.pop_front();
        const int i = u / W, j = u % W;
        const auto push0 = [&](const int v) {
            if (dist[v] > dist[u]) {
                dist[v] = dist[u];
                parent[v] = u;
                que.push_front(v);
            }
        };
        const auto push1 = [&](const int v) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                que.push_back(v);
            }
        };
        if (grid[u] == '<' and j > 0) push0(u - 1);
        if (grid[u] == '>' and j + 1 < W) push0(u + 1);
        if (grid[u] == '^' and i > 0) push0(u - W);
        if (grid[u] == 'v' and i + 1 < H) push0(u + W);
        if (j > 0) push1(u - 1);
        if (j + 1 < W) push1(u + 1);
        if (i > 0) push1(u - W);
        if (i + 1 < H) push1(u + W);
    }
    std::cout << dist[dst] - 1 << '\n';
    while (parent[dst] != src) {
        const int prv = parent[dst];
        if (prv - 1 == dst) grid[prv] = '<';
        if (prv + 1 == dst) grid[prv] = '>';
        if (prv - W == dst) grid[prv] = '^';
        if (prv + W == dst) grid[prv] = 'v';
        dst = prv;
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            std::cout << grid[i * W + j];
        }
        std::cout << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 47 ms 5576 KB Output is correct
7 Correct 39 ms 6196 KB Output is correct
8 Correct 103 ms 14048 KB Output is correct
9 Correct 180 ms 24456 KB Output is correct
10 Correct 249 ms 33944 KB Output is correct
11 Correct 263 ms 40900 KB Output is correct