Submission #480275

#	Time	Username	Problem	Language	Result	Execution time	Memory
480275		Jarif_Rahman	Patkice II (COCI21_patkice2)	C++17	110 / 110	1118 ms	413592 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<str> s(n);
    for(str &ss: s) cin >> ss;
    vector<vector<pair<int, ll>>> v(n*m);
    int ss, ee;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(s[i][j] == 'o') ss = i*m + j;
        if(s[i][j] == 'x') ee = i*m + j; 
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(j != 0){
            v[i*m + j].pb({i*m + j - 1, s[i][j] != '<' && s[i][j] != 'o'});
        }
        if(j != m-1){
            v[i*m + j].pb({i*m + j + 1, s[i][j] != '>' && s[i][j] != 'o'});
        }
        if(i != 0){
            v[i*m + j].pb({(i-1)*m + j, s[i][j] != '^' && s[i][j] != 'o'});
        }
        if(i != n-1){
            v[i*m + j].pb({(i+1)*m + j, s[i][j] != 'v' && s[i][j] != 'o'});
        }
    }
    vector<ll> dis(n*m, inf);
    deque<pair<int, int>> d;
    vector<int> ls(n*m, -1);
    vector<bool> bl(n*m, 0);
    dis[ss] = 0;
    d.pb({ss, -1});
    while(!d.empty()){
        auto [nd, lss] = d.back(); d.pop_back();
        if(bl[nd]) continue;
        bl[nd] = 1;
        ls[nd] = lss;
        for(auto p: v[nd]) if(dis[nd] + p.sc < dis[p.f]){
            dis[p.f] = dis[nd] + p.sc;
            ls[p.f] = nd;
            if(p.sc == 0) d.pb({p.f, nd});
            else d.push_front({p.f, nd});
        }
    }
    int nd = ee;
    while(1){
        int x = ls[nd];
        int a = x/m, b = x%m;
        if(x == ss || x == -1) break;
        if(x == nd-1) s[a][b] = '>';
        if(x == nd+1) s[a][b] = '<';
        if(x == nd-m) s[a][b] = 'v';
        if(x == nd+m) s[a][b] = '^';
        nd = x;
    }
    cout << dis[ee] << "\n";
    for(str x: s) cout << x << "\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:55:22: warning: 'ee' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         int x = ls[nd];
      |                      ^
Main.cpp:57:9: warning: 'ss' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |         if(x == ss || x == -1) break;
      |         ^~

• Subtask 1: 30 / 30
• Subtask 2: 80 / 80