Submission #381970

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
381970	2021-03-26T08:12:38 Z	Vimmer	Patkice II (COCI21_patkice2)	C++14	110 / 110	1125 ms	95212 KB

Main

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define N 100500
#define PB push_back
#define endl '\n'
#define pri(x) cout << x << endl
#define _ << " " <<
#define sz(x) int(x.size())
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;

//typedef tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ord_set;

int f[2005][2005];

pair <int, int> from[2005][2005];

int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("1.in", "r", stdin);

    for (int i = 0; i < 2005; i++)
        for (int j = 0; j < 2005; j++)
            f[i][j] = 1e9;

    int n, m;

    cin >> n >> m;

    string s[n];

    for (int i = 0; i < n; i++)
        cin >> s[i];

    set <pair <int, pair <int, int> > > se; se.clear();

    int xs, ys, xf, yf;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == 'o')
            {
                xs = i; ys = j;
            }

            if (s[i][j] == 'x')
            {
                xf = i; yf = j;
            }
        }

    f[xs][ys] = 0;

    se.insert({0, {xs, ys}});

    while (sz(se))
    {
        pair <int, int> pt = (*se.begin()).S;

        se.erase(se.begin());

        int i = pt.F, j = pt.S;

        if (s[i][j] == 'x')
            break;

        int cx = pt.F, cy = pt.S;

        if (s[i][j] == '>')
            cy++;
                else if (s[i][j] == '<')
                    cy--;
                        else if (s[i][j] == '^')
                            cx--;
                                else if (s[i][j] == 'v')
                                    cx++;

        if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[i][j])
        {
            f[cx][cy] = f[i][j];

            from[cx][cy] = {i, j};

            se.insert({f[cx][cy], {cx, cy}});
        }

        int b[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

        for (int i = 0; i < 4; i++)
        {
            int cx = pt.F + b[i][0];

            int cy = pt.S + b[i][1];

            if (0 <= cx && cx < n && cy >= 0 && cy < m && f[cx][cy] > f[pt.F][pt.S] + 1)
            {
                f[cx][cy] = f[pt.F][pt.S] + 1;

                from[cx][cy] = {pt.F, pt.S};

                se.insert({f[cx][cy], {cx, cy}});
            }
        }
    }

    pri(f[xf][yf] - 1);

    while (xf != xs || yf != ys)
    {
        pair <int, int> pt = from[xf][yf];

        char c;

        if (pt.S < yf)
            c = '>';
                else if (pt.S > yf)
                    c = '<';
                        else if (pt.F > xf)
                            c = '^';
                                else c = 'v';
        xf = pt.F;

        yf = pt.S;

        s[xf][yf] = c;
    }

    s[xs][ys] = 'o';

    for (int i = 0; i < n; i++)
        cout << s[i] << endl;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:139:13: warning: 'ys' may be used uninitialized in this function [-Wmaybe-uninitialized]
  139 |     s[xs][ys] = 'o';
      |             ^
Main.cpp:47:9: warning: 'xs' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |     int xs, ys, xf, yf;
      |         ^~
Main.cpp:117:17: warning: 'yf' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |     pri(f[xf][yf] - 1);
      |                 ^
Main.cpp:117:17: warning: 'xf' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16108 KB	Output is correct
2	Correct	10 ms	16108 KB	Output is correct
3	Correct	10 ms	16108 KB	Output is correct
4	Correct	10 ms	16108 KB	Output is correct
5	Correct	10 ms	16108 KB	Output is correct

Subtask #2

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	16108 KB	Output is correct
2	Correct	10 ms	16108 KB	Output is correct
3	Correct	10 ms	16108 KB	Output is correct
4	Correct	10 ms	16108 KB	Output is correct
5	Correct	10 ms	16108 KB	Output is correct
6	Correct	73 ms	21356 KB	Output is correct
7	Correct	106 ms	31468 KB	Output is correct
8	Correct	227 ms	30060 KB	Output is correct
9	Correct	468 ms	60268 KB	Output is correct
10	Correct	626 ms	49004 KB	Output is correct
11	Correct	1125 ms	95212 KB	Output is correct