oj.uz

Submission #1084229

# Submission time Handle Problem Language Result Execution time Memory
1084229 2024-09-05T16:26:55 Z anhthi Patkice II (COCI21_patkice2) C++14
110 / 110
 280 ms 78204 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 6 ms 16988 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 6 ms 16984 KB Output is correct
4 Correct 6 ms 16984 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16988 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 6 ms 16984 KB Output is correct
4 Correct 6 ms 16984 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 46 ms 26448 KB Output is correct
7 Correct 43 ms 29524 KB Output is correct
8 Correct 110 ms 40276 KB Output is correct
9 Correct 167 ms 56408 KB Output is correct
10 Correct 267 ms 66896 KB Output is correct
11 Correct 280 ms 78204 KB Output is correct