oj.uz

Submission #209263

# Submission time Handle Problem Language Result Execution time Memory
209263 2020-03-13T14:15:02 Z Blerargh Nautilus (BOI19_nautilus) C++17
66 / 100
 1000 ms 100088 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef pair<ld,ld> id;

#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define ROF(i, a, b) for(int i=(a); i>=(b); i--)
#define MEM(x, v) memset(x, v, sizeof(x))
#define FILL(x, n, v) fill(x, x+n, v)
#define SORT(x) sort((x).begin(), (x).end())
#define CMPSORT(x, cp) sort((x).begin(), (x).end(), cp)
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define f first
#define s second
#define ins insert
#define e emplace
#define eb emplace_back
#define ef emplace_front
#define p push
#define pf push_front
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ft front
#define bk back
#define pp pop
#define ppb pop_back
#define ppf pop_front

#define db cout<<"YEET\n";
#define ct(x) cout<<x<<'\n';

const ll MOD = 1e9+7; //998244353
const ll MX = 5e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);

int main(){
    FAST
    ll r, c, m;
    string dirs;
    cin >> r >> c >> m;

    char grid[505][505];
    FOR(i,1,r){
        FOR(j,1,c){
            cin >> grid[i][j];
        }
    }

    cin >> dirs;

    set<ll> checked[505][505];
    queue<tuple<ll,ll,ll> > bfs; //r, c, id
    ll cnt=0;
    ll y[4] = {-1, 0, 1, 0}, x[4] = {0, 1, 0, -1}; //nesw

    FOR(i,1,r){
        FOR(j,1,c){
            if (grid[i][j]=='#') continue;

            bfs.e(i,j,0);
            while (!bfs.empty()){
                ll row, col, idx;
                tie(row, col, idx) = bfs.ft();
                bfs.pp();

                if (checked[row][col].count(idx)) continue;
                else checked[row][col].ins(idx);

                if (idx == m) {
                    cnt++;
                    continue;
                }

                if (dirs[idx] == 'N'){
                    row--;
                    if (!row || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'E'){
                    col++;
                    if (col>c || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'S'){
                    row++;
                    if (row>r || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }
                if (dirs[idx] == 'W'){
                    col--;
                    if (!col || grid[row][col]=='#') continue;
                    bfs.e(row,col,idx+1);
                }

                if (dirs[idx] == '?'){
                    FOR(k,0,3){
                        ll newrow = row+y[k];
                        ll newcol = col+x[k];
                        if (newrow == 0 || newrow > r || newcol == 0 || newcol > c) continue;
                        if (grid[newrow][newcol]=='#') continue;
                        bfs.e(newrow, newcol, idx+1);
                    }
                }
            }
        }
    }
    cout << cnt;
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 55932 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 13 ms 12536 KB Output is correct
6 Correct 12 ms 12408 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 55932 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 13 ms 12536 KB Output is correct
6 Correct 12 ms 12408 KB Output is correct
7 Correct 297 ms 59896 KB Output is correct
8 Correct 57 ms 20984 KB Output is correct
9 Correct 21 ms 14328 KB Output is correct
10 Correct 15 ms 12920 KB Output is correct
11 Correct 13 ms 12536 KB Output is correct
12 Correct 539 ms 61048 KB Output is correct
13 Correct 311 ms 48504 KB Output is correct
14 Correct 159 ms 34936 KB Output is correct
15 Correct 18 ms 13560 KB Output is correct
16 Correct 13 ms 12536 KB Output is correct
17 Correct 569 ms 61176 KB Output is correct
18 Correct 358 ms 52220 KB Output is correct
19 Correct 98 ms 29436 KB Output is correct
20 Correct 38 ms 18424 KB Output is correct
21 Correct 13 ms 12536 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 55932 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 14 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 13 ms 12536 KB Output is correct
6 Correct 12 ms 12408 KB Output is correct
7 Correct 297 ms 59896 KB Output is correct
8 Correct 57 ms 20984 KB Output is correct
9 Correct 21 ms 14328 KB Output is correct
10 Correct 15 ms 12920 KB Output is correct
11 Correct 13 ms 12536 KB Output is correct
12 Correct 539 ms 61048 KB Output is correct
13 Correct 311 ms 48504 KB Output is correct
14 Correct 159 ms 34936 KB Output is correct
15 Correct 18 ms 13560 KB Output is correct
16 Correct 13 ms 12536 KB Output is correct
17 Correct 569 ms 61176 KB Output is correct
18 Correct 358 ms 52220 KB Output is correct
19 Correct 98 ms 29436 KB Output is correct
20 Correct 38 ms 18424 KB Output is correct
21 Correct 13 ms 12536 KB Output is correct
22 Execution timed out 1103 ms 100088 KB Time limit exceeded
23 Halted 0 ms 0 KB -