oj.uz

Submission #925659

# Submission time Handle Problem Language Result Execution time Memory
925659 2024-02-12T07:05:32 Z vjudge1 Nautilus (BOI19_nautilus) C++17
29 / 100
 1000 ms 1468 KB 
#include<iostream>
#include<cassert>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<map>

using namespace std;

const int N = (int)4e5 + 7;
const int inf = (int)1e9 + 7;
const int MOD = (int)998244353;
const long long INF = (long long)1e18 + 7; 

int mult(int x, int y) {
	return 1ll*x*y%MOD;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) {
		x -= MOD;
	}
	return x;
}

int sub(int x, int y) {
	x -= y;
	if(x < 0) {
		x += MOD;
	}
	return x;
}

int n, m, k;

vector<pair<int, int> > dir[300];

void init() {
	dir['W'] = {{0, -1}};
	dir['E'] = {{0, +1}};
	dir['N'] = {{-1, 0}};
	dir['S'] = {{+1, 0}};
	dir['?'] = {{0, -1}, {0, +1}, {-1, 0}, {+1, 0}};
}

int main() {	
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	init();
	cin >> n >> m >> k;
	char a[n+1][m+1];
	bool is[n+1][m+1];
	bool used[k+1][n+1][m+1];
	memset(used, 0, sizeof(used));
	memset(is, 0, sizeof(is));
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	string s;
	cin >> s;
	s = '#'+s;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(a[i][j] == '#') {
				continue;
			}
			memset(used, 0, sizeof(used));
			queue<pair<int, pair<int, int> > > q;
			q.push({0, {i, j}});
			used[0][i][j] = 1;
			while(!q.empty()) {
				int x = q.front().second.first;
				int y = q.front().second.second;
			    int id = q.front().first;
				q.pop();
				if(id == k) {
					is[x][y] = 1;
					continue;
				}
				for(auto e : dir[s[id+1]]) {
					int tox = x+e.first;
					int toy = y+e.second;
					if(tox<1 || tox>n || toy<1 || toy>m || a[tox][toy] == '#' || used[id+1][tox][toy]) {
						continue;
					}
					used[id+1][tox][toy] = 1;
					q.push({id+1, {tox, toy}});
				}
			}					
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			ans += is[i][j];
		}
	}
	cout << ans << "\n";
	return 0;
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:87:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |     for(auto e : dir[s[id+1]]) {
      |                             ^

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1468 KB Output is correct
2 Correct 120 ms 1468 KB Output is correct
3 Correct 94 ms 1368 KB Output is correct
4 Correct 64 ms 1464 KB Output is correct
5 Correct 34 ms 1368 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1468 KB Output is correct
2 Correct 120 ms 1468 KB Output is correct
3 Correct 94 ms 1368 KB Output is correct
4 Correct 64 ms 1464 KB Output is correct
5 Correct 34 ms 1368 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Execution timed out 1080 ms 1372 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 1468 KB Output is correct
2 Correct 120 ms 1468 KB Output is correct
3 Correct 94 ms 1368 KB Output is correct
4 Correct 64 ms 1464 KB Output is correct
5 Correct 34 ms 1368 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Execution timed out 1080 ms 1372 KB Time limit exceeded
8 Halted 0 ms 0 KB -