oj.uz

답안 #929070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
929070 2024-02-17T16:12:26 Z Amirreza_Fakhri Patkice II (COCI21_patkice2) C++17
110 / 110
 820 ms 316572 KB 
// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;
 
const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 2e3+5;
 
int r, s, si, so, d[maxn*maxn], par[maxn*maxn], cnt[maxn*maxn];
char t[maxn][maxn];
vector <pii> adj[maxn*maxn];
deque <int> q;
 
bool val(int i, int j) {
    return min(i ,j) >= 0 and i < r and j < s;
}
 
int id(int i, int j) {
    return i*maxn+j;
}
 
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> s;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) {
            cin >> t[i][j];
            if (t[i][j] == 'o') si = id(i, j);
            if (t[i][j] == 'x') so = id(i, j);
            int x = i+1, y = j+0, w = 1;
            if (val(x, y)) {
                if (t[i][j] == 'o' or t[i][j] == 'v') w = 0;
                adj[id(i, j)].pb(mp(id(x, y), w));
            }
            x = i-1, y = j+0, w = 1;
            if (val(x, y)) {
                if (t[i][j] == 'o' or t[i][j] == '^') w = 0;
                adj[id(i, j)].pb(mp(id(x, y), w));
            }
            x = i+0, y = j+1, w = 1;
            if (val(x, y)) {
                if (t[i][j] == 'o' or t[i][j] == '>') w = 0;
                adj[id(i, j)].pb(mp(id(x, y), w));
            }
            x = i+0, y = j-1, w = 1;
            if (val(x, y)) {
                if (t[i][j] == 'o' or t[i][j] == '<') w = 0;
                adj[id(i, j)].pb(mp(id(x, y), w));
            }
        }
    }
    memset(d, 63, sizeof d);
    d[si] = 0;
    q.push_front(si);
    while (q.size()) {
        int v = q.front(); q.pop_front();
        cnt[v]++;
        assert(cnt[v] <= 2);
        for (pii e : adj[v]) {
            int u = e.F;
            if (d[v]+e.S < d[u]) {
                d[u] = d[v]+e.S;
                par[u] = v;
                if (e.S) q.push_back(u);
                else q.push_front(u);
            }
        }
    }
    int v = so;
    while (v != si) {
        int u  = par[v];
        int i = u/maxn, j = u%maxn;
        if (v == u+1) {
            if (!(t[i][j] == 'o' or t[i][j] == '>')) t[i][j] = '>';
        }
        if (v == u-1) {
            if (!(t[i][j] == 'o' or t[i][j] == '<')) t[i][j] = '<';
        }
        if (v == u+maxn) {
            if (!(t[i][j] == 'o' or t[i][j] == 'v')) t[i][j] = 'v';
        }
        if (v == u-maxn) {
            if (!(t[i][j] == 'o' or t[i][j] == '^')) t[i][j] = '^';
        }
        v = u;
    }
    cout << d[so] << '\n';
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < s; j++) cout << t[i][j];
        cout << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 113076 KB Output is correct
2 Correct 26 ms 112984 KB Output is correct
3 Correct 25 ms 112984 KB Output is correct
4 Correct 26 ms 113248 KB Output is correct
5 Correct 28 ms 112984 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 113076 KB Output is correct
2 Correct 26 ms 112984 KB Output is correct
3 Correct 25 ms 112984 KB Output is correct
4 Correct 26 ms 113248 KB Output is correct
5 Correct 28 ms 112984 KB Output is correct
6 Correct 116 ms 147320 KB Output is correct
7 Correct 146 ms 154132 KB Output is correct
8 Correct 293 ms 193104 KB Output is correct
9 Correct 518 ms 243332 KB Output is correct
10 Correct 601 ms 294576 KB Output is correct
11 Correct 820 ms 316572 KB Output is correct