oj.uz

Submission #496417

# Submission time Handle Problem Language Result Execution time Memory
496417 2021-12-21T07:41:11 Z Ierus Nautilus (BOI19_nautilus) C++17
66 / 100
 403 ms 262148 KB 
#include<bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
*/
using namespace std;
#pragma GCC optimize ("unroll-loops,Ofast,O3")
#pragma GCC target("avx,avx2,fma")
#define F first
#define int short
#define S second
#define sz(x) (int)x.size()
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define NFS ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long ll;
const long long inf = 1e18+777;
const int N = 5555;
const bool I = 1;
const vector<pair<int,int>> dxy = {{1,0},{-1,0},{0,1},{0,-1}};
int n, m, k, q[5555];
char a[555][555];
bool vis[555][555];
int32_t res = 0;
bool used[555][555][5555];
bool In(int x, int y){
	return (x <= n && x >= 1 && y <= m && y >= 1);
}
void bfs(int x, int y, int d = 1){
	deque<tuple<int,int,int>> dq;
	dq.pb({x, y, d});
	while(!dq.empty()){
		tie(x, y, d) = dq.front();
		dq.pop_front();
		if(d == k + 1){
			if(!vis[x][y]){
				vis[x][y] = true;
				++res;
			}
			continue;	
		}
		if(q[d] == -1){
			for(auto [f, s] : dxy){
				int x1 = x + f, y1 = y + s;
				if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){
					dq.pb({x1, y1, d+1});
					used[x1][y1][d+1] = true;
				}
			}
		}else{
			int x1 = x + dxy[q[d]].F, y1 = y + dxy[q[d]].S;
			if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){
				dq.pb({x1, y1, d+1});
				used[x1][y1][d+1] = true;
			}
		}
	}
}
void dfs(int x, int y, int d){
	if(d == k + 1){
		if(!vis[x][y]){
			vis[x][y] = true;
			++res;
		}
		return;
	}
	if(q[d] == -1){
		for(auto [f, s] : dxy){
			int x1 = x + f, y1 = y + s;
			if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){
				used[x1][y1][d+1] = true;
				dfs(x1, y1, d+1);
			}
		}
	}else{
		int x1 = x + dxy[q[d]].F, y1 = y + dxy[q[d]].S;
		if(In(x1, y1) && a[x1][y1] != '#' && !used[x1][y1][d+1]){
			used[x1][y1][d+1] = true;
			dfs(x1, y1, d+1);
		}
	}
}
signed main(){NFS;
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= k; ++i){
		char r; cin >> r;
		if(r == '?') q[i] = -1;
		if(r == 'N') q[i] = 1;
		if(r == 'S') q[i] = 0;
		if(r == 'E') q[i] = 2;
		if(r == 'W') q[i] = 3;
	}

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j){
			if(a[i][j] == '.'){
				dfs(i, j, 1);
			}
		}
	cout << res;
};

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41796 KB Output is correct
2 Correct 19 ms 31280 KB Output is correct
3 Correct 10 ms 15692 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 1 ms 600 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41796 KB Output is correct
2 Correct 19 ms 31280 KB Output is correct
3 Correct 10 ms 15692 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 38 ms 41764 KB Output is correct
8 Correct 16 ms 23588 KB Output is correct
9 Correct 9 ms 12620 KB Output is correct
10 Correct 3 ms 5708 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 46 ms 41836 KB Output is correct
13 Correct 39 ms 33856 KB Output is correct
14 Correct 28 ms 24752 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 58 ms 41884 KB Output is correct
18 Correct 47 ms 33804 KB Output is correct
19 Correct 15 ms 15308 KB Output is correct
20 Correct 5 ms 5836 KB Output is correct
21 Correct 1 ms 588 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 41796 KB Output is correct
2 Correct 19 ms 31280 KB Output is correct
3 Correct 10 ms 15692 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 38 ms 41764 KB Output is correct
8 Correct 16 ms 23588 KB Output is correct
9 Correct 9 ms 12620 KB Output is correct
10 Correct 3 ms 5708 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 46 ms 41836 KB Output is correct
13 Correct 39 ms 33856 KB Output is correct
14 Correct 28 ms 24752 KB Output is correct
15 Correct 4 ms 5836 KB Output is correct
16 Correct 1 ms 588 KB Output is correct
17 Correct 58 ms 41884 KB Output is correct
18 Correct 47 ms 33804 KB Output is correct
19 Correct 15 ms 15308 KB Output is correct
20 Correct 5 ms 5836 KB Output is correct
21 Correct 1 ms 588 KB Output is correct
22 Runtime error 403 ms 262148 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -