oj.uz

Submission #929063

# Submission time Handle Problem Language Result Execution time Memory
929063 2024-02-17T15:55:58 Z Amirreza_Fakhri Patkice II (COCI21_patkice2) C++17
55 / 110
 701 ms 288776 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];
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();
        for (pii e : adj[v]) {
            int u = e.F;
            if (d[v]+e.S < d[u]) {
                d[u] = d[v]+e.S;
                if (e.S) q.push_back(u);
                else q.push_front(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
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 54 ms 112436 KB Partially correct
2 Partially correct 25 ms 112476 KB Partially correct
3 Partially correct 25 ms 112488 KB Partially correct
4 Partially correct 25 ms 112464 KB Partially correct
5 Partially correct 26 ms 112216 KB Partially correct

Subtask #2
40.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 54 ms 112436 KB Partially correct
2 Partially correct 25 ms 112476 KB Partially correct
3 Partially correct 25 ms 112488 KB Partially correct
4 Partially correct 25 ms 112464 KB Partially correct
5 Partially correct 26 ms 112216 KB Partially correct
6 Partially correct 105 ms 138748 KB Partially correct
7 Partially correct 135 ms 140116 KB Partially correct
8 Partially correct 232 ms 176880 KB Partially correct
9 Partially correct 459 ms 219392 KB Partially correct
10 Partially correct 584 ms 267012 KB Partially correct
11 Partially correct 701 ms 288776 KB Partially correct