oj.uz

Submission #1021372

# Submission time Handle Problem Language Result Execution time Memory
1021372 2024-07-12T17:21:20 Z ilovveyyou Patkice II (COCI21_patkice2) C++14
110 / 110
 335 ms 77968 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define clz __builtin_clzll
#define ctz __builtin_ctzll
#define popcount __builtin_popcount
#define lg(x) (63 - clz(x))

template <class X, class Y>
    inline bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        return false;
    }
template <class X, class Y>
    inline bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        return false;
    }
template <class X>
    inline void compress(vector<X> &a) {
        sort(all(a)); a.resize(unique(all(a)) - a.begin());
    }

const ll oo = (ll) 1e17;
const int inf = (int) 1e9, mod = (int) 1e9 + 7;

struct Info {
    int x, y;
    char dir;
};

const int mxn = (int) 2e3 + 5, lg = (int) 19;
int r, c;
char a[mxn][mxn];

int f[mxn][mxn];
Info trace[mxn][mxn];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
char d[] = {'>', '<', 'v', '^'};

bool isIn(int x, int y) {
    return 1 <= x && x <= r && 1 <= y && y <= c;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> r >> c;
    for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j)
        cin >> a[i][j];

    pair<int, int> s, t;
    for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j) {
        if (a[i][j] == 'o')
            s = mp(i, j);
        else if (a[i][j] == 'x')
            t = mp(i, j);
    }

    memset(f, 0x3f, sizeof f);

    deque<pii> dq;
    dq.push_back(s);
    f[s.fi][s.se] = 0;
    trace[s.fi][s.se] = {-1, -1, '!'};

    while (!dq.empty()) {
        pii top = dq.front(); dq.pop_front();
        int u = top.fi, v = top.se;
        if (top == t) continue;
        for (int i = 0; i < 4; ++i) {
            int x = u + dx[i];
            int y = v + dy[i];
            if (!isIn(x, y)) continue;
            if (a[u][v] != '.' && (d[i] == a[u][v] || a[u][v] == 'o')) {
                if (minimize(f[x][y], f[u][v])) {
                    trace[x][y] = {u, v, d[i]};
                    dq.push_front(mp(x, y));
                }
            } else {
                if (minimize(f[x][y], f[u][v] + 1)) {
                    trace[x][y] = {u, v, d[i]};
                    dq.push_back(mp(x, y));
                }
            }
        }
    }

    int u = t.fi, v = t.se;
    cout << f[u][v] << '\n';
    while (trace[u][v].x != -1) {
        int x = trace[u][v].x;
        int y = trace[u][v].y;
        if (mp(x, y) != s)
            a[x][y] = trace[u][v].dir;

        u = x; v = y;
    }
    for (int i = 1; i <= r; ++i)
    for (int j = 1; j <= c; ++j)
        cout << a[i][j] << (j == c ? "\n" : "");

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16076 KB Output is correct
2 Correct 7 ms 16216 KB Output is correct
3 Correct 7 ms 16220 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 7 ms 16188 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16076 KB Output is correct
2 Correct 7 ms 16216 KB Output is correct
3 Correct 7 ms 16220 KB Output is correct
4 Correct 7 ms 16220 KB Output is correct
5 Correct 7 ms 16188 KB Output is correct
6 Correct 49 ms 26392 KB Output is correct
7 Correct 49 ms 29520 KB Output is correct
8 Correct 119 ms 40272 KB Output is correct
9 Correct 190 ms 56404 KB Output is correct
10 Correct 328 ms 66784 KB Output is correct
11 Correct 335 ms 77968 KB Output is correct