oj.uz

Submission #209290

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

#pragma GCC optimize("Ofast")

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 202 ms 55800 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 15 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 12 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 202 ms 55800 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 15 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 12 ms 12536 KB Output is correct
6 Correct 12 ms 12408 KB Output is correct
7 Correct 297 ms 59952 KB Output is correct
8 Correct 57 ms 20984 KB Output is correct
9 Correct 22 ms 14328 KB Output is correct
10 Correct 14 ms 12920 KB Output is correct
11 Correct 13 ms 12536 KB Output is correct
12 Correct 538 ms 61100 KB Output is correct
13 Correct 303 ms 48504 KB Output is correct
14 Correct 155 ms 35064 KB Output is correct
15 Correct 17 ms 13560 KB Output is correct
16 Correct 13 ms 12536 KB Output is correct
17 Correct 566 ms 61304 KB Output is correct
18 Correct 344 ms 52216 KB Output is correct
19 Correct 95 ms 29432 KB Output is correct
20 Correct 39 ms 18552 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 202 ms 55800 KB Output is correct
2 Correct 22 ms 15224 KB Output is correct
3 Correct 15 ms 13176 KB Output is correct
4 Correct 13 ms 12664 KB Output is correct
5 Correct 12 ms 12536 KB Output is correct
6 Correct 12 ms 12408 KB Output is correct
7 Correct 297 ms 59952 KB Output is correct
8 Correct 57 ms 20984 KB Output is correct
9 Correct 22 ms 14328 KB Output is correct
10 Correct 14 ms 12920 KB Output is correct
11 Correct 13 ms 12536 KB Output is correct
12 Correct 538 ms 61100 KB Output is correct
13 Correct 303 ms 48504 KB Output is correct
14 Correct 155 ms 35064 KB Output is correct
15 Correct 17 ms 13560 KB Output is correct
16 Correct 13 ms 12536 KB Output is correct
17 Correct 566 ms 61304 KB Output is correct
18 Correct 344 ms 52216 KB Output is correct
19 Correct 95 ms 29432 KB Output is correct
20 Correct 39 ms 18552 KB Output is correct
21 Correct 13 ms 12536 KB Output is correct
22 Execution timed out 1099 ms 100208 KB Time limit exceeded
23 Halted 0 ms 0 KB -