Submission #929065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
929065	2024-02-17T16:03:22 Z	Amirreza_Fakhri	Patkice II (COCI21_patkice2)	C++17	110 / 110	796 ms	300888 KB

Main

// 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];
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;
                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

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	113752 KB	Output is correct
2	Correct	26 ms	113748 KB	Output is correct
3	Correct	25 ms	113756 KB	Output is correct
4	Correct	27 ms	113756 KB	Output is correct
5	Correct	26 ms	113752 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	113752 KB	Output is correct
2	Correct	26 ms	113748 KB	Output is correct
3	Correct	25 ms	113756 KB	Output is correct
4	Correct	27 ms	113756 KB	Output is correct
5	Correct	26 ms	113752 KB	Output is correct
6	Correct	141 ms	145752 KB	Output is correct
7	Correct	133 ms	149076 KB	Output is correct
8	Correct	243 ms	187216 KB	Output is correct
9	Correct	451 ms	231016 KB	Output is correct
10	Correct	556 ms	279580 KB	Output is correct
11	Correct	796 ms	300888 KB	Output is correct