oj.uz

답안 #479537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
479537 2021-10-12T06:11:14 Z kakayoshi Patkice II (COCI21_patkice2) C++14
110 / 110
 1367 ms 112920 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[2005][2005],n,m,a[2005][2005];
pi father[2005][2005];
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;
    cout<<dp[t.fi][t.se]-1<<endl;
    while (x!=s.fi || y!=s.se)
    {
        forw(huong,1,4)
        if (father[x][y].fi+tx[huong]==x && father[x][y].se+ty[huong]==y)
        {
            a[father[x][y].fi][father[x][y].se]=huong;
            break;
        }
        int new_x=father[x][y].fi;
        int new_y=father[x][y].se;
        x=new_x;
        y=new_y;
    }
    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<pii, vector <pii>, greater<pii> > p;
    forw(i,1,n)
        forw(j,1,m)
            forw(k,1,4)
                dp[i][j]=1e9;
    dp[x][y]=0;
    p.pu({0,{x,y}});
    while (!p.empty())
    {
        int val=p.top().fi;
        x=p.top().se.fi;
        y=p.top().se.se;
        p.pop();
        if (val>dp[x][y]) continue;
        ////////////////
        forw(huong,1,4)
        {
            int xx=x+tx[huong];
            int yy=y+ty[huong];
            int dodai=val+(huong!=a[x][y]);
            if (check(xx,yy) && dodai<dp[xx][yy])
            {
                father[xx][yy]={x,y};
                dp[xx][yy]=dodai;
                p.pu({dodai,{xx,yy}});
            }
        }
        ///////////////
    }
    return;
}
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;
            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
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 332 KB Output is correct

Subtask #2
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 160 ms 19956 KB Output is correct
7 Correct 182 ms 26120 KB Output is correct
8 Correct 388 ms 43276 KB Output is correct
9 Correct 863 ms 70816 KB Output is correct
10 Correct 958 ms 88836 KB Output is correct
11 Correct 1367 ms 112920 KB Output is correct