oj.uz

Submission #373526

# Submission time Handle Problem Language Result Execution time Memory
373526 2021-03-05T01:14:20 Z Fysty Patkice (COCI20_patkice) C++17
50 / 50
 2 ms 876 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll INF=1e18;
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define F first
#define S second
#define pb push_back
ll dist[105][105];
char dir='X';
vector<pll> ed[105][105];
void dijk(ll sx,ll sy,ll ex,ll ey)
{
    queue<pll> q;
    q.push({sx,sy});
    dist[sx][sy]=0;
    while(!q.empty())
    {
        pll p=q.front();q.pop();
        for(auto u:ed[p.F][p.S])
        {
            if(dist[u.F][u.S]<=dist[p.F][p.S]+1)
            {
                if(dist[u.F][u.S]==dist[p.F][p.S]+1&&u.F==ex&&u.S==ey)
                {
                    if(u.F==p.F-1) dir=min(dir,'S');
                    else if(u.F==p.F+1) dir=min(dir,'N');
                    else if(u.S==p.S-1) dir=min(dir,'E');
                    else dir=min(dir,'W');
                }
                continue;
            }
            dist[u.F][u.S]=dist[p.F][p.S]+1;
            if(u.F==ex&&u.S==ey)
            {
                if(u.F==p.F-1) dir=min(dir,'S');
                else if(u.F==p.F+1) dir=min(dir,'N');
                else if(u.S==p.S-1) dir=min(dir,'E');
                else dir=min(dir,'W');
            }
            q.push(u);
        }
    }
}
string s[105];
int main()
{
    MottoHayaku
    ll n,m,sx,sy,ex,ey;
    cin>>n>>m;
    rep(i,n) cin>>s[i];
    rep(i,n)
    {
        rep(j,m)
        {
            dist[i][j]=INF;
            if(s[i][j]=='^') ed[i-1][j].pb({i,j});
            if(s[i][j]=='v') ed[i+1][j].pb({i,j});
            if(s[i][j]=='<') ed[i][j-1].pb({i,j});
            if(s[i][j]=='>') ed[i][j+1].pb({i,j});
            if(s[i][j]=='x') sx=i,sy=j;
            if(s[i][j]=='o')
            {
                ex=i,ey=j;
                ed[i-1][j].pb({i,j});
                ed[i+1][j].pb({i,j});
                ed[i][j-1].pb({i,j});
                ed[i][j+1].pb({i,j});
            }
        }
    }
    dijk(sx,sy,ex,ey);
    if(dist[ex][ey]==INF) cout<<":(\n";
    else cout<<":)\n"<<dir<<"\n";
}

Compilation message

patkice.cpp: In function 'int main()':
patkice.cpp:77:19: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |     if(dist[ex][ey]==INF) cout<<":(\n";
      |        ~~~~~~~~~~~^
patkice.cpp:77:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
patkice.cpp:76:9: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     dijk(sx,sy,ex,ey);
      |     ~~~~^~~~~~~~~~~~~
patkice.cpp:76:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 1 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 1 ms 620 KB Output is correct