Submission #1074938

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1074938	2024-08-25T16:56:08 Z	TrinhKhanhDung	Patkice II (COCI21_patkice2)	C++14	110 / 110	236 ms	58232 KB

Main

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n + 3, vector<char>(m + 3, 0));
    int sx, sy, tx, ty;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            if(a[i][j] == 'o'){
                sx = i;
                sy = j;
            }
            if(a[i][j] == 'x'){
                tx = i;
                ty = j;
            }
        }
    }

    vector<vector<int>> dist(n + 3, vector<int>(m + 3, INF));
    vector<vector<pair<int, int>>> trace(n + 3, vector<pair<int, int>>(m + 3));
    dist[tx][ty] = 0;
    deque<pair<int, int>> dq;
    dq.push_back(make_pair(tx, ty));

    while(sz(dq)){
        int x = dq.front().fi;
        int y = dq.front().se;
        dq.pop_front();
//        cout << x << ' ' << y << ' ' << dist[x][y] << '\n';

        //x - 1, y
        if(x > 1){
            if(minimize(dist[x - 1][y], dist[x][y] + (a[x - 1][y] != 'v'))){
                if(a[x - 1][y] == 'v') dq.push_front(make_pair(x - 1, y));
                else dq.push_back(make_pair(x - 1, y));
                trace[x - 1][y] = make_pair(x, y);
            }
        }

        //x + 1, y
        if(x < n){
            if(minimize(dist[x + 1][y], dist[x][y] + (a[x + 1][y] != '^'))){
                if(a[x + 1][y] == '^') dq.push_front(make_pair(x + 1, y));
                else dq.push_back(make_pair(x + 1, y));
                trace[x + 1][y] = make_pair(x, y);
            }
        }

        //x, y - 1
        if(y > 1){
            if(minimize(dist[x][y - 1], dist[x][y] + (a[x][y - 1] != '>'))){
                if(a[x][y - 1] == '>') dq.push_front(make_pair(x, y - 1));
                else dq.push_back(make_pair(x, y - 1));
                trace[x][y - 1] = make_pair(x, y);
            }
        }

        //x, y + 1
        if(y < m){
            if(minimize(dist[x][y + 1], dist[x][y] + (a[x][y + 1] != '<'))){
                if(a[x][y + 1] == '<') dq.push_front(make_pair(x, y + 1));
                else dq.push_back(make_pair(x, y + 1));
                trace[x][y + 1] = make_pair(x, y);
            }
        }
    }

    cout << dist[sx][sy] - 1 << '\n';
    int x = sx, y = sy;
    while(x != tx || y != ty){
//        cout << x << ' ' << y << '\n';
        int nx = trace[x][y].fi, ny = trace[x][y].se;
        if(a[x][y] != 'o'){
            if(nx < x) a[x][y] = '^';
            if(nx > x) a[x][y] = 'v';
            if(ny < y) a[x][y] = '<';
            if(ny > y) a[x][y] = '>';
        }
        x = nx;
        y = ny;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cout << a[i][j];
        }
        cout << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
   // freopen("task.inp", "r", stdin);
   // freopen("task.out", "w", stdout);

    int t = 1;
   // cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:100:19: warning: 'ty' may be used uninitialized in this function [-Wmaybe-uninitialized]
  100 |     while(x != tx || y != ty){
      |           ~~~~~~~~^~~~~~~~~~
Main.cpp:100:19: warning: 'tx' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:100:19: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:100:19: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	30 ms	7752 KB	Output is correct
7	Correct	35 ms	9560 KB	Output is correct
8	Correct	88 ms	19280 KB	Output is correct
9	Correct	135 ms	37248 KB	Output is correct
10	Correct	201 ms	46420 KB	Output is correct
11	Correct	236 ms	58232 KB	Output is correct