Submission #479506

#	Time	Username	Problem	Language	Result	Execution time	Memory
479506		kakayoshi	Patkice II (COCI21_patkice2)	C++14	0 / 110	1 ms	460 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pi;
typedef pair<ll, pair<ll, ll> > pii;
typedef vector <ll> vi;
typedef pair <  ll, vector <ll> > super;
#define forw(i,a,b) for (ll i=a;i<=(b);i++)
#define forb(i,a,b) for (ll i=a;i>=(b);i--)
#define fast {ios::sync_with_stdio(false); cin.tie(0); }
#define fi first
#define se second
#define pu push
#define puf push_front
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fr front
#define all(a) a.begin(),a.end()
const ll oo=1e18;
const ll mod=1e9+7;
const int base=31;
const int tx[5]={0,-1,0,1,0};
const int ty[5]={0,0,1,0,-1};
const ll maxN=2e5+5;
int dp[2500][2500][10],n,m,a[2500][2500];
pii father[2500][2500][10];
pi s,t;
bool check(int x, int y)
{
    if (1<=x && x<=n)
        if (1<=y && y<=m) return true;
    return false;
}
void print()
{
    int x=t.fi;
    int y=t.se;
    int huong=1;
    cout<<dp[t.fi][t.se][1]-1<<"/n";
    while (x!=s.fi || y!=s.se)
    {
        //cout<<x<<" "<<y<<" "<<huong<<endl;
        a[x][y]=huong;
        int new_huong=father[x][y][huong].fi;
        int new_x=father[x][y][huong].se.fi;
        int new_y=father[x][y][huong].se.se;
        x=new_x;
        y=new_y;
        huong=new_huong;
    }
    forw(i,1,n)
    {
        forw(j,1,m)
        {
            if (i==t.fi && j==t.se) cout<<'x';
            else if (i==s.fi && j==s.se) cout<<'o';
            else if (a[i][j]==0) cout<<'.';
            else if (a[i][j]==1) cout<<'^';
            else if (a[i][j]==2) cout<<'>';
            else if (a[i][j]==3) cout<<'v';
            else cout<<'<';
        }
        cout<<"/n";
    }
    return;
}
void dijk(int x, int y)
{
    priority_queue<super, vector <super>, greater<super> > p;
    forw(i,1,n)
        forw(j,1,m)
            forw(k,1,4)
                dp[i][j][k]=1e9;
    forw(i,1,4)
    {
        dp[x][y][i]=0;
        p.pu({0,{x,y,i}});
    }
    while (!p.empty())
    {
        int val=p.top().fi;
        x=p.top().se[0];
        y=p.top().se[1];
        int huong=p.top().se[2];
        p.pop();
        if (val>dp[x][y][huong]) continue;
        ////////////////
        int xx=x+tx[huong];
        int yy=y+ty[huong];
        if (!check(xx,yy)) continue;
        forw(i,1,4)
        if (a[xx][yy]!=i)
        {
            if (val+1<dp[xx][yy][i])
            {
                father[xx][yy][i]={huong,{x,y}};
                dp[xx][yy][i]=val+1;
                p.pu({val+1,{xx,yy,i}});
            }
        }
        else
            if (val<dp[xx][yy][i])
            {
                father[xx][yy][i]={huong,{x,y}};
                dp[xx][yy][i]=val;
                p.pu({val,{xx,yy,i}});
            }
        ///////////////
    }
    return;
}
void solve()
{
    scanf("%d%d",&n,&m);
    s={0,0};
    t={0,0};
    forw(i,1,n)
        forw(j,1,m)
        {
            char c;
            scanf("%c",&c);
            if (c=='^') a[i][j]=1;
            else
                if (c=='>') a[i][j]=2;
                else
                    if (c=='v') a[i][j]=3;
                    else
                        if (c=='<') a[i][j]=4;
            if (c=='o') s={i,j};
            if (c=='x') t={i,j};
        }
    dijk(s.fi,s.se);
    print();
}
int main()
{
    fast;
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:123:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |             scanf("%c",&c);
      |             ~~~~~^~~~~~~~~

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