oj.uz

답안 #479504

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479504 2021-10-12T04:31:48 Z kakayoshi Patkice II (COCI21_patkice2) C++17
15 / 110
 2000 ms 524288 KB 
#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<<endl;
    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<<endl;
    }
    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 (x==t.fi && y==t.se) return;
        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}});
            }
        ///////////////
    }
}
void solve()
{
    cin>>n>>m;
    s={0,0};
    t={0,0};
    forw(i,1,n)
        forw(j,1,m)
        {
            char c;
            cin>>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;
                        else a[i][j]=5;
            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;
}

Subtask #1
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 332 KB Partially correct
2 Partially correct 1 ms 460 KB Partially correct
3 Partially correct 1 ms 588 KB Partially correct
4 Partially correct 1 ms 588 KB Partially correct
5 Partially correct 1 ms 332 KB Partially correct

Subtask #2
0.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 1 ms 332 KB Partially correct
2 Partially correct 1 ms 460 KB Partially correct
3 Partially correct 1 ms 588 KB Partially correct
4 Partially correct 1 ms 588 KB Partially correct
5 Partially correct 1 ms 332 KB Partially correct
6 Partially correct 483 ms 93472 KB Partially correct
7 Partially correct 881 ms 175440 KB Partially correct
8 Partially correct 1716 ms 284232 KB Partially correct
9 Execution timed out 2110 ms 524288 KB Time limit exceeded
10 Halted 0 ms 0 KB -