oj.uz

Submission #699450

# Submission time Handle Problem Language Result Execution time Memory
699450 2023-02-17T02:55:10 Z Chal1shkan Patkice (COCI20_patkice) C++14
50 / 50
 1 ms 596 KB 
# include <bits/stdc++.h>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll maxn = 1e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {0, -1, 1, 0};
const ll dy[] = {1, 0, 0, -1};
const ld eps = 1e-6;

using namespace std;

ll n, m;
char c[103][103];
ll d[103][103][4];
ll st_x = -1, st_y = -1;
ll fn_x = -1, fn_y = -1;

pair <ll, ll> dir (char c)
{
    if (c == '>') return {0, 1};
    if (c == '^') return {-1, 0};
    if (c == 'v') return {1, 0};
    if (c == '<') return {0, -1};
    return {0, 0};
}

void dijkstra (ll xx, ll yy, ll k)
{
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= m; ++j)
        {
            d[i][j][k] = inf;
        }
    }
    if (c[xx][yy] == '.') return; 
    d[st_x][st_y][k] = 0;
    d[xx][yy][k] = 1;
    set < pair <ll, pair <ll, ll> > > q;
    q.insert({d[xx][yy][k], {xx, yy}});
    while (!q.empty())
    {
        ll x = (q.begin() -> ss.ff);
        ll y = (q.begin() -> ss.ss);
        q.erase(q.begin());
        pair <ll, ll> qw = dir(c[x][y]);
        ll to_x = x + qw.ff;
        ll to_y = y + qw.ss;
        if (d[to_x][to_y][k] > d[x][y][k] + 1 && (c[to_x][to_y] != '.' && c[to_x][to_y] != 'o'))
        {
            q.erase({d[to_x][to_y][k], {to_x, to_y}});
            d[to_x][to_y][k] = d[x][y][k] + 1;
            q.insert({d[to_x][to_y][k], {to_x, to_y}});
        }
    }
}

void ma1n ()
{
    cin >> n >> m;
    for (ll i = 1; i <= n; ++i)
    {
        for (ll j = 1; j <= m; ++j)
        {
            cin >> c[i][j];
            if (c[i][j] == 'o')
            {
                st_x = i;
                st_y = j;
            }
            if (c[i][j] == 'x')
            {
                fn_x = i;
                fn_y = j;
            }
        }
    }
    ll mn = inf;
    for (ll k = 0; k < 4; ++k)
    {
        ll x = st_x + dx[k];
        ll y = st_y + dy[k];
        dijkstra(x, y, k);
        mn = min(mn, d[fn_x][fn_y][k]);
        //cout << d[fn_x][fn_y][k] << nl;
    }
    for (ll k = 0; k < 4 && mn != inf; ++k)
    {
        if (d[fn_x][fn_y][k] == mn)
        {
            cout << ":)" << nl;
            if (k == 0) cout << "E";
            if (k == 1) cout << "N";
            if (k == 2) cout << "S";
            if (k == 3) cout << "W";
            return;
        }
    }
    cout << ":(";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 332 KB Output is correct