Submission #1135197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135197		DangKhoizzzz	Patkice II (COCI21_patkice2)	C++17	110 / 110	858 ms	352184 KiB

Main

//-----------------(boost)-----------------//
#pragma GCC target ("avx2")                //
#pragma GCC optimization ("O3")            //
#pragma GCC optimization ("unroll-loops")  //
//---------------------------------------- //

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair <short , short>
#define arr3 array <short , 3>

using namespace std;

const int INF = 1e9 + 7;
const int maxn = 2e3 + 1;

int n , m , sx , sy , ex , ey , d[maxn][maxn];
pii trace[maxn][maxn];
vector <arr3> g[maxn][maxn];
char a[maxn][maxn];
bool vis[maxn][maxn];

int dx[4] = {0 , 0 , 1 , -1};
int dy[4] = {1 , -1 , 0 , 0};

void bfs01()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) d[i][j] = INF;
    }

    deque <pii> Q;
    Q.push_back({sx , sy});
    d[sx][sy] = 0;

    int pass = 0;

    while(!Q.empty())
    {
        int i = Q.front().fi;
        int j = Q.front().se;
        Q.pop_front();

        pass++;

        if(vis[i][j]) continue;
        vis[i][j] = 1;

        for(arr3 tmp: g[i][j])
        {
            int x = tmp[0];
            int y = tmp[1];
            int w = tmp[2];

            if(d[x][y] > d[i][j] + w)
            {
                d[x][y] = d[i][j] + w;
                trace[x][y] = {i , j};
                if(w == 0) Q.push_front({x , y});
                else Q.push_back({x , y});
            }
        }
    }
    cout << d[ex][ey] << '\n';
}

void trace_back()
{
    int i = ex , j = ey;

    while(true)
    {
        int x = trace[i][j].fi;
        int y = trace[i][j].se;

        if(x == i-1) a[x][y] = 'v';
        if(x == i+1) a[x][y] = '^';
        if(y == j-1) a[x][y] = '>';
        if(y == j+1) a[x][y] = '<';
        i = x , j = y;
        if(i == sx && j == sy) break;
    }
    a[sx][sy] = 'o';

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++) cout << a[i][j];
        cout << '\n';
    }
}

void solve()
{
    cin >> n >> m;
    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(j > 1) g[i][j].push_back({i , j-1 , 0});
                if(j < m) g[i][j].push_back({i , j+1 , 0});
                if(i > 1) g[i][j].push_back({i-1 , j , 0});
                if(i < n) g[i][j].push_back({i+1 , j , 0});

            }
            else if(a[i][j] == 'x')
            {
                 ex = i , ey = j;
            }
            else
            {
                if(a[i][j] == '<' && j > 1) g[i][j].push_back({i , j-1 , 0});
                if(a[i][j] == '>' && j < m) g[i][j].push_back({i , j+1 , 0});
                if(a[i][j] == '^' && i > 1) g[i][j].push_back({i-1 , j , 0});
                if(a[i][j] == 'v' && i < n) g[i][j].push_back({i+1 , j , 0});

                for(int k = 0; k < 4; k++)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];

                    if(x == 0 || x == n+1 || y == 0 || y == m+1) continue;

                    g[i][j].push_back({x , y , 1});
                }
            }
        }
    }
    bfs01();
    trace_back();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:107:46: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  107 |                 if(j > 1) g[i][j].push_back({i , j-1 , 0});
      |                                              ^
Main.cpp:107:51: warning: narrowing conversion of '(j - 1)' from 'int' to 'short int' [-Wnarrowing]
  107 |                 if(j > 1) g[i][j].push_back({i , j-1 , 0});
      |                                                  ~^~
Main.cpp:108:46: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  108 |                 if(j < m) g[i][j].push_back({i , j+1 , 0});
      |                                              ^
Main.cpp:108:51: warning: narrowing conversion of '(j + 1)' from 'int' to 'short int' [-Wnarrowing]
  108 |                 if(j < m) g[i][j].push_back({i , j+1 , 0});
      |                                                  ~^~
Main.cpp:109:47: warning: narrowing conversion of '(i - 1)' from 'int' to 'short int' [-Wnarrowing]
  109 |                 if(i > 1) g[i][j].push_back({i-1 , j , 0});
      |                                              ~^~
Main.cpp:109:52: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
  109 |                 if(i > 1) g[i][j].push_back({i-1 , j , 0});
      |                                                    ^
Main.cpp:110:47: warning: narrowing conversion of '(i + 1)' from 'int' to 'short int' [-Wnarrowing]
  110 |                 if(i < n) g[i][j].push_back({i+1 , j , 0});
      |                                              ~^~
Main.cpp:110:52: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
  110 |                 if(i < n) g[i][j].push_back({i+1 , j , 0});
      |                                                    ^
Main.cpp:119:64: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  119 |                 if(a[i][j] == '<' && j > 1) g[i][j].push_back({i , j-1 , 0});
      |                                                                ^
Main.cpp:119:69: warning: narrowing conversion of '(j - 1)' from 'int' to 'short int' [-Wnarrowing]
  119 |                 if(a[i][j] == '<' && j > 1) g[i][j].push_back({i , j-1 , 0});
      |                                                                    ~^~
Main.cpp:120:64: warning: narrowing conversion of 'i' from 'int' to 'short int' [-Wnarrowing]
  120 |                 if(a[i][j] == '>' && j < m) g[i][j].push_back({i , j+1 , 0});
      |                                                                ^
Main.cpp:120:69: warning: narrowing conversion of '(j + 1)' from 'int' to 'short int' [-Wnarrowing]
  120 |                 if(a[i][j] == '>' && j < m) g[i][j].push_back({i , j+1 , 0});
      |                                                                    ~^~
Main.cpp:121:65: warning: narrowing conversion of '(i - 1)' from 'int' to 'short int' [-Wnarrowing]
  121 |                 if(a[i][j] == '^' && i > 1) g[i][j].push_back({i-1 , j , 0});
      |                                                                ~^~
Main.cpp:121:70: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
  121 |                 if(a[i][j] == '^' && i > 1) g[i][j].push_back({i-1 , j , 0});
      |                                                                      ^
Main.cpp:122:65: warning: narrowing conversion of '(i + 1)' from 'int' to 'short int' [-Wnarrowing]
  122 |                 if(a[i][j] == 'v' && i < n) g[i][j].push_back({i+1 , j , 0});
      |                                                                ~^~
Main.cpp:122:70: warning: narrowing conversion of 'j' from 'int' to 'short int' [-Wnarrowing]
  122 |                 if(a[i][j] == 'v' && i < n) g[i][j].push_back({i+1 , j , 0});
      |                                                                      ^
Main.cpp:131:40: warning: narrowing conversion of 'x' from 'int' to 'short int' [-Wnarrowing]
  131 |                     g[i][j].push_back({x , y , 1});
      |                                        ^
Main.cpp:131:44: warning: narrowing conversion of 'y' from 'int' to 'short int' [-Wnarrowing]
  131 |                     g[i][j].push_back({x , y , 1});
      |                                            ^

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