oj.uz

Submission #497984

# Submission time Handle Problem Language Result Execution time Memory
497984 2021-12-24T07:49:17 Z dannyboy20031204 Patkice II (COCI21_patkice2) C++17
110 / 110
 286 ms 112240 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define fi first
#define se second
#define mp make_pair 
using namespace std;
void db() {cout << endl;}
template <typename T, typename ...U> void db(T a, U ...b) {
    //return;
    cout << a << ' ', db(b...);
}
#ifdef Cloud
#define file freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define file ios::sync_with_stdio(false); cin.tie(0)
#endif
const int inf = 1e9, N = 2001, mod = 1e9 + 7;
bool vis[N][N]{};
int dis[N][N]{}, n, m;
pair<int, int> par[N][N], st, ed;
deque<pair<int, int>> q;
void add(int i, int j, int a, int b, int d){
    if (i < 0 or j < 0 or i >= n or j >= m) return;
    if (dis[a][b] + d >= dis[i][j]) return;
    dis[i][j] = dis[a][b] + d;
    par[i][j] = {a, b};
    if (d) q.push_back({i, j});
    else q.push_front({i, j});
}
signed main(){
    file;
    cin >> n >> m;
    string s[n];
    for (string &i : s) cin >> i;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (s[i][j] == 'o'){
                q.push_back({i, j});
                vis[i][j] = true;
                st = {i, j};
            }
            if (s[i][j] == 'x'){
                ed = {i, j};
            }
            dis[i][j] = inf;
        }
    }
    dis[st.fi][st.se] = 0;
    while (!q.empty()){
        auto u = q.front();
        q.pop_front();
        if (s[u.fi][u.se] == '<') add(u.fi, u.se - 1, u.fi, u.se, 0);
        if (s[u.fi][u.se] == '>') add(u.fi, u.se + 1, u.fi, u.se, 0);
        if (s[u.fi][u.se] == '^') add(u.fi - 1, u.se, u.fi, u.se, 0);
        if (s[u.fi][u.se] == 'v') add(u.fi + 1, u.se, u.fi, u.se, 0);

        add(u.fi, u.se - 1, u.fi, u.se, 1);
        add(u.fi, u.se + 1, u.fi, u.se, 1);
        add(u.fi - 1, u.se, u.fi, u.se, 1);
        add(u.fi + 1, u.se, u.fi, u.se, 1);
    }
    cout << dis[ed.fi][ed.se] - 1 << '\n';
    while (ed != st){
        auto pre = par[ed.fi][ed.se];
        if (dis[pre.fi][pre.se] != dis[ed.fi][ed.se] and pre != st){
            if (ed.fi == pre.fi + 1) s[pre.fi][pre.se] = 'v';
            if (ed.fi == pre.fi - 1) s[pre.fi][pre.se] = '^';
            if (ed.se == pre.se + 1) s[pre.fi][pre.se] = '>';
            if (ed.se == pre.se - 1) s[pre.fi][pre.se] = '<';
        }
        ed = pre;
    }
    for (string i : s) cout << i << '\n';
}

Subtask #1
30.0 / 30.0

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

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 34 ms 17856 KB Output is correct
7 Correct 39 ms 22680 KB Output is correct
8 Correct 107 ms 41704 KB Output is correct
9 Correct 156 ms 71268 KB Output is correct
10 Correct 241 ms 88876 KB Output is correct
11 Correct 286 ms 112240 KB Output is correct