/**
* author: wxhtzdy
* created: 20.01.2023 20:24:06
**/
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const string D = "NSWE";
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k, n, m;
cin >> k >> n >> m;
string d;
cin >> d;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
vector<vector<int>> id(n, vector<int>(m));
vector<vector<int>> par(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
id[i][j] = i * m + j;
par[i][j] = id[i][j];
}
}
vector<int> len(1 << 4);
for (int mask = 0; mask < (1 << 4); mask++) {
int bal = 0;
for (int i = 0; i < k; i++) {
bool ok = false;
for (int j = 0; j < 4; j++) {
if ((mask >> j & 1) && D[j] == d[i]) {
ok = true;
}
}
bal = (ok ? bal + 1 : 0);
len[mask] = max(len[mask], bal);
}
if (len[mask] == k) {
len[mask] = (int) 1e9;
} else {
int L = 0;
while (L < k) {
bool ok = false;
for (int j = 0; j < 4; j++) {
if ((mask >> j & 1) && D[j] == d[L]) {
ok = true;
}
}
if (ok) {
L += 1;
} else {
break;
}
}
int R = k - 1;
while (R >= 0) {
bool ok = false;
for (int j = 0; j < 4; j++) {
if ((mask >> j & 1) && D[j] == d[R]) {
ok = true;
}
}
if (ok) {
R -= 1;
} else {
break;
}
}
assert(L <= R);
len[mask] = max(len[mask], L + (k - 1 - R));
}
}
function<int(int, int)> Get = [&](int x, int y) {
return par[x][y] == id[x][y] ? id[x][y] : par[x][y] = Get(par[x][y] / m, par[x][y] % m);
};
auto Valid = [&](int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m && a[x][y] != 0;
};
vector<vector<int>> v(n, vector<int>(m));
auto Update = [&](vector<int> q) {
for (int i = 0; i < (int) q.size(); i++) {
int x = q[i] / m;
int y = q[i] % m;
v[x][y] = (int) q.size();
}
};
for (int iter = 0; iter < 20; iter++) {
vector<int> f;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] != 0 && Get(i, j) == id[i][j]) {
f.push_back(id[i][j]);
}
}
}
vector<vector<bool>> was(n, vector<bool>(m));
for (int i = 0; i < (int) f.size(); i++) {
if (was[f[i] / m][f[i] % m]) {
continue;
}
vector<int> que(1, f[i]);
int idx = -1;
for (int b = 0; b < (int) que.size(); b++) {
int x = que[b] / m;
int y = que[b] % m;
was[x][y] = true;
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (Valid(nx, ny) && !was[nx][ny]) {
int mask = 0;
if (Valid(nx - 1, ny) && was[nx - 1][ny]) {
mask ^= (1 << 0);
}
if (Valid(nx + 1, ny) && was[nx + 1][ny]) {
mask ^= (1 << 1);
}
if (Valid(nx, ny - 1) && was[nx][ny - 1]) {
mask ^= (1 << 2);
}
if (Valid(nx, ny + 1) && was[nx][ny + 1]) {
mask ^= (1 << 3);
}
if (len[mask] >= a[nx][ny]) {
was[nx][ny] = true;
que.push_back(id[nx][ny]);
if (Get(nx, ny) != f[i]) {
idx = Get(nx, ny);
break;
}
}
}
}
if (idx != -1) {
break;
}
}
for (auto& p : que) {
was[p / m][p % m] = false;
}
if (idx != -1) {
int x = f[i] / m;
int y = f[i] % m;
par[x][y] = idx;
} else {
Update(que);
}
}
}
int res = (int) 1e9;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] > 0) {
res = min(res, v[i][j]);
}
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (v[i][j] == res) {
cnt += 1;
}
}
}
cout << res << " " << cnt << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
2 |
Correct |
858 ms |
14616 KB |
Output is correct |
3 |
Correct |
302 ms |
14616 KB |
Output is correct |
4 |
Correct |
302 ms |
14616 KB |
Output is correct |
5 |
Correct |
1452 ms |
17196 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1276 ms |
16120 KB |
Output is correct |
8 |
Correct |
566 ms |
7812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
8 ms |
468 KB |
Output is correct |
3 |
Correct |
7 ms |
468 KB |
Output is correct |
4 |
Correct |
8 ms |
468 KB |
Output is correct |
5 |
Correct |
8 ms |
468 KB |
Output is correct |
6 |
Correct |
12 ms |
528 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
7 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
340 KB |
Output is correct |
10 |
Correct |
8 ms |
532 KB |
Output is correct |
11 |
Correct |
3 ms |
340 KB |
Output is correct |
12 |
Correct |
6 ms |
340 KB |
Output is correct |
13 |
Correct |
8 ms |
468 KB |
Output is correct |
14 |
Correct |
8 ms |
468 KB |
Output is correct |
15 |
Correct |
8 ms |
532 KB |
Output is correct |
16 |
Correct |
9 ms |
488 KB |
Output is correct |
17 |
Correct |
8 ms |
344 KB |
Output is correct |
18 |
Correct |
5 ms |
396 KB |
Output is correct |
19 |
Correct |
17 ms |
540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
340 KB |
Output is correct |
2 |
Correct |
858 ms |
14616 KB |
Output is correct |
3 |
Correct |
302 ms |
14616 KB |
Output is correct |
4 |
Correct |
302 ms |
14616 KB |
Output is correct |
5 |
Correct |
1452 ms |
17196 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1276 ms |
16120 KB |
Output is correct |
8 |
Correct |
566 ms |
7812 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
8 ms |
468 KB |
Output is correct |
11 |
Correct |
7 ms |
468 KB |
Output is correct |
12 |
Correct |
8 ms |
468 KB |
Output is correct |
13 |
Correct |
8 ms |
468 KB |
Output is correct |
14 |
Correct |
12 ms |
528 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
7 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
340 KB |
Output is correct |
18 |
Correct |
8 ms |
532 KB |
Output is correct |
19 |
Correct |
3 ms |
340 KB |
Output is correct |
20 |
Correct |
6 ms |
340 KB |
Output is correct |
21 |
Correct |
8 ms |
468 KB |
Output is correct |
22 |
Correct |
8 ms |
468 KB |
Output is correct |
23 |
Correct |
8 ms |
532 KB |
Output is correct |
24 |
Correct |
9 ms |
488 KB |
Output is correct |
25 |
Correct |
8 ms |
344 KB |
Output is correct |
26 |
Correct |
5 ms |
396 KB |
Output is correct |
27 |
Correct |
17 ms |
540 KB |
Output is correct |
28 |
Correct |
1403 ms |
20580 KB |
Output is correct |
29 |
Correct |
341 ms |
17764 KB |
Output is correct |
30 |
Correct |
280 ms |
16196 KB |
Output is correct |
31 |
Correct |
359 ms |
15780 KB |
Output is correct |
32 |
Correct |
370 ms |
15712 KB |
Output is correct |
33 |
Correct |
553 ms |
16004 KB |
Output is correct |
34 |
Correct |
1368 ms |
20484 KB |
Output is correct |
35 |
Correct |
991 ms |
15032 KB |
Output is correct |
36 |
Correct |
1083 ms |
16424 KB |
Output is correct |
37 |
Correct |
1056 ms |
16348 KB |
Output is correct |
38 |
Correct |
1330 ms |
20504 KB |
Output is correct |
39 |
Correct |
765 ms |
17072 KB |
Output is correct |
40 |
Correct |
843 ms |
17128 KB |
Output is correct |
41 |
Correct |
396 ms |
16068 KB |
Output is correct |
42 |
Correct |
1149 ms |
16736 KB |
Output is correct |
43 |
Correct |
290 ms |
16232 KB |
Output is correct |
44 |
Correct |
579 ms |
7732 KB |
Output is correct |