oj.uz

Submission #319574

# Submission time Handle Problem Language Result Execution time Memory
319574 2020-11-05T14:14:28 Z BeanZ Patkice (COCI20_patkice) C++14
50 / 50
 5 ms 5612 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
vector<ll> node[N];
ll vis[N], d[N];
vector<ll> topo;
void dfs(ll u){
    vis[u] = 1;
    for (auto j : node[u]){
        if (!vis[j]) dfs(j);
    }
    topo.push_back(u);
}
ll r, s;
ll get(ll i, ll j){
    return (i - 1) * s + j;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> r >> s;
    ll st, ed;
    pair<ll, ll> stt;
    for (int i = 1; i <= r; i++){
        for (int j = 1; j <= s; j++){
            char c;
            cin >> c;
            if (c == 'o') st = get(i, j), stt = {i, j};
            if (c == 'x') ed = get(i, j);
            if (c == '>') node[get(i, j)].push_back(get(i, j + 1));
            if (c == '<') node[get(i, j)].push_back(get(i, j - 1));
            if (c == '^') node[get(i, j)].push_back(get(i - 1, j));
            if (c == 'v') node[get(i, j)].push_back(get(i + 1, j));
        }
    }
    for (int i = 1; i <= (r * s); i++){
        if (!vis[i]) dfs(i);
        d[i] = 1e9;
        //cout << "[[" << i << "]]" << endl;
        //for (auto j: node[i]){
         //   cout << j << " ";
        //}
        //cout << endl;
    }
    d[ed] = 0;
    //cout << ed << endl;
    reverse(topo.begin(), topo.end());
    while (topo.size()){
        ll x = topo.back();
        //cout << x << " ";
        topo.pop_back();
        for (auto j : node[x]){
            d[x] = min(d[x], d[j] + 1);
        }
        //cout << x << " " << d[x] << endl;
    }
    ll res = 1e9;
    char ans;
    if (stt.second < s){
        if (res > d[get(stt.first, stt.second + 1)]){
            res = d[get(stt.first, stt.second + 1)];
            ans = 'E';
        }
    }
    if (stt.first > 1){
        if (res > d[get(stt.first - 1, stt.second)]){
            res = d[get(stt.first - 1, stt.second)];
            ans = 'N';
        }
    }
    if (stt.first < r){
        if (res > d[get(stt.first + 1, stt.second)]){
            res = d[get(stt.first + 1, stt.second)];
            ans = 'S';
        }
    }if (stt.second > 1){
        if (res > d[get(stt.first, stt.second - 1)]){
            res = d[get(stt.first, stt.second - 1)];
            ans = 'W';
        }
    }
    if (res < 1e9){
        cout << ":)" << endl;
        cout << ans;
    } else {
        cout << ":(";
    }
}
/*
*/

Compilation message

patkice.cpp: In function 'int main()':
patkice.cpp:29:8: warning: variable 'st' set but not used [-Wunused-but-set-variable]
   29 |     ll st, ed;
      |        ^~
patkice.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   25 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
patkice.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   26 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
patkice.cpp:52:11: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |     d[ed] = 0;
      |     ~~~~~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5356 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5348 KB Output is correct
6 Correct 4 ms 5228 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5228 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5372 KB Output is correct
8 Correct 4 ms 5228 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 5 ms 5612 KB Output is correct
11 Correct 4 ms 5224 KB Output is correct
12 Correct 5 ms 5356 KB Output is correct
13 Correct 4 ms 5228 KB Output is correct
14 Correct 4 ms 5356 KB Output is correct
15 Correct 4 ms 5228 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 4 ms 5228 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 4 ms 5228 KB Output is correct