Submission #873092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
873092	2023-11-14T12:38:58 Z	kh0i	Patkice II (COCI21_patkice2)	C++17	110 / 110	891 ms	392612 KB

Main

/**
 *	author: kh0i
 *	created: 18.08.2022 20:41:18
**/
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;

const int N = 2e3 + 5;

int r, s, d[N][N], vis[N][N];
pair<int, int> st, en;
char a[N][N];
vector<pair<pair<int, int>, int>> adj[N][N];
pair<int, int> trace[N][N];

void solve(){
    cin >> r >> s;
    for(int i = 1; i <= r; ++i){
        for(int j = 1; j <= s; ++j){
            cin >> a[i][j];
            if(a[i][j] == 'o') st = {i, j};
            if(a[i][j] == 'x') en = {i, j};
            d[i][j] = 1e9;
        }
    }
    for(int i = 1; i <= r; ++i){
        for(int j = 1; j <= s; ++j){
            // up
            if(i - 1 > 0){
                if(a[i][j] == '^') adj[i][j].push_back({{i - 1, j}, 0});
                else adj[i][j].push_back({{i - 1, j}, 1});
            }
            // down
            if(i + 1 <= r){
                if(a[i][j] == 'v') adj[i][j].push_back({{i + 1, j}, 0});
                else adj[i][j].push_back({{i + 1, j}, 1});
            }
            // left
            if(j - 1 > 0){
                if(a[i][j] == '<') adj[i][j].push_back({{i, j - 1}, 0});
                else adj[i][j].push_back({{i, j - 1}, 1});
            }
            if(j + 1 <= s){
                if(a[i][j] == '>') adj[i][j].push_back({{i, j + 1}, 0});
                else adj[i][j].push_back({{i, j + 1}, 1});
            }
        }
    }

    // 0 - 1 BFS
    deque<pair<int, int>> q;
    q.push_back(st);
    d[st.first][st.second] = -1;
    trace[st.first][st.second] = st;
    while(!q.empty()){
        int x = q.front().first, y = q.front().second;
        q.pop_front();
        vis[x][y] = 1;
        for(auto k : adj[x][y]){
            int i = k.first.first, j = k.first.second, w = k.second;
            if(vis[i][j]) continue;
            if(d[x][y] + w < d[i][j]){
                trace[i][j] = {x, y};
                d[i][j] = d[x][y] + w;
                if(w == 0) q.push_front({i, j});
                else q.push_back({i, j});
            }
        } 
    }
    int ans = d[en.first][en.second];
    debug(ans, trace[en.first][en.second]);
    int i = en.first, j = en.second;
    while(i != st.first or j != st.second){
        int x = trace[i][j].first, y = trace[i][j].second;
        if(x == i + 1){
            a[i + 1][j] = '^';
        }
        else if(x == i - 1){
            a[i - 1][j] = 'v';
        }
        else if(y == j + 1){
            a[i][j + 1] = '<';
        }
        else if(y == j - 1){
            a[i][j - 1] = '>';
        }
        else{
            assert(0);
        }
        debug(i, j, x, y);
        i = x,j = y;
    }
    a[i][j] = 'o';
    cout << ans << '\n';
    for(int i = 1; i <= r; ++i){
        for(int j = 1; j <= s; ++j){
            cout << a[i][j];
        }   
        cout << "\n";
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	100944 KB	Output is correct
2	Correct	22 ms	100820 KB	Output is correct
3	Correct	22 ms	103004 KB	Output is correct
4	Correct	22 ms	102972 KB	Output is correct
5	Correct	21 ms	100956 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	100944 KB	Output is correct
2	Correct	22 ms	100820 KB	Output is correct
3	Correct	22 ms	103004 KB	Output is correct
4	Correct	22 ms	102972 KB	Output is correct
5	Correct	21 ms	100956 KB	Output is correct
6	Correct	127 ms	152400 KB	Output is correct
7	Correct	148 ms	164144 KB	Output is correct
8	Correct	295 ms	221264 KB	Output is correct
9	Correct	516 ms	289020 KB	Output is correct
10	Correct	690 ms	359508 KB	Output is correct
11	Correct	891 ms	392612 KB	Output is correct