oj.uz

Submission #480275

# Submission time Handle Problem Language Result Execution time Memory
480275 2021-10-15T12:42:17 Z Jarif_Rahman Patkice II (COCI21_patkice2) C++17
110 / 110
 1118 ms 413592 KB 
#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

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.0 / 30.0

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

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 139 ms 58180 KB Output is correct
7 Correct 160 ms 61248 KB Output is correct
8 Correct 390 ms 149320 KB Output is correct
9 Correct 661 ms 249724 KB Output is correct
10 Correct 981 ms 363720 KB Output is correct
11 Correct 1118 ms 413592 KB Output is correct