#include <bits/stdc++.h>
using namespace std;
constexpr int dx[]{-1, 0, 1, 0}, dy[]{0, 1, 0, -1};
struct DSU {
vector<int> p, sz;
vector<vector<int>> subtree;
DSU() = default;
DSU(int n) : p(n), sz(n, 1), subtree(n) {
iota(p.begin(), p.end(), 0);
for (int i = 0; i < n; ++i) {
subtree[i] = {i};
}
}
int leader(int x) {
return x == p[x] ? x : p[x] = leader(p[x]);
}
bool unite(int a, int b) {
a = leader(a), b = leader(b);
if (a == b) {
return false;
}
if (sz[a] < sz[b]) {
swap(a, b);
}
subtree[a].insert(subtree[a].end(), subtree[b].begin(), subtree[b].end());
subtree[b].clear();
p[b] = a;
sz[a] += sz[b];
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int M, n, m;
cin >> M >> n >> m;
string str;
cin >> str;
vector<int> s(M);
for (int i = 0; i < M; ++i) {
char c = str[i];
s[i] = c == 'N' ? 0 : c == 'E' ? 1 : c == 'S' ? 2 : 3;
}
vector u(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> u[i][j];
}
}
const int N = n * m;
vector dead(16, vector(n, vector<bool>(m)));
for (int mask = 1; mask < 16; ++mask) {
vector<bool> yay(M);
for (int i = 0; i < M; ++i) {
if (mask >> s[i] & 1) {
yay[i] = true;
}
}
int mx = 0;
int first = -1e9, last = -1e9;
for (int i = 0, j = 0; i < M; i = j) {
while (j < M && yay[i] == yay[j]) {
j += 1;
}
if (yay[i]) {
mx = max(mx, j - i);
if (i == 0) {
first = j - i;
} else if (j == M) {
last = j - i;
}
}
}
mx = max(mx, first + last);
if (mx == M) {
mx = numeric_limits<int>::max();
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dead[mask][i][j] = u[i][j] && u[i][j] <= mx;
}
}
}
DSU d(N);
auto check = [&](int i, int j, int a) -> bool {
int mask = 0;
for (int k = 0; k < 4; ++k) {
int ni = i + dx[k], nj = j + dy[k];
if (ni >= 0 && ni < n && nj >= 0 && nj < m && d.leader(ni * m + nj) == a) {
mask |= 1 << k;
}
}
return dead[mask][i][j];
};
int ans = numeric_limits<int>::max();
int cnt = 0;
vector<bool> in_stk(N);
vector was(n, vector<bool>(m));
for (int ii = 0; ii < n; ++ii) {
for (int jj = 0; jj < m; ++jj) {
if (was[ii][jj] || u[ii][jj] == 0) {
continue;
}
vector<int> stk;
vector<vector<int>> consider;
int i = ii, j = jj;
consider.push_back({i * m + j});
stk.push_back(i * m + j);
was[i][j] = true;
in_stk[i * m + j] = true;
bool ok = true;
while (!consider.back().empty()) {
const int now = consider.back().back();
int x = now / m, y = now % m;
bool pop = true;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
const int to = nx * m + ny;
if (d.leader(to) == d.leader(now)) {
continue;
}
if (check(nx, ny, i * m + j)) {
int lead = d.leader(nx * m + ny);
if (in_stk[lead]) {
int pnt = consider.size() - 1;
for (; pnt >= 0; --pnt) {
if (stk[pnt] == lead) {
break;
}
}
for (int p = pnt + 1; p < consider.size(); ++p) {
if (consider[pnt].size() < consider[p].size()) {
swap(consider[pnt], consider[p]);
}
for (int yy : consider[p]) {
consider[pnt].push_back(yy);
}
}
pair<int, int> mx = {-1, -1};
for (int p = pnt; p < stk.size(); ++p) {
mx = max(mx, pair{int(d.subtree[stk[p]].size()), p});
}
for (int p = pnt; p < consider.size(); ++p) {
if (p != mx.second) {
for (int yy: d.subtree[stk[p]]) {
consider[pnt].push_back(yy);
}
}
}
for (int aa = pnt; aa < consider.size() - 1; ++aa) {
d.unite(stk[aa], i * m + j);
}
for (int aa = pnt; aa < stk.size(); ++aa) {
in_stk[stk[aa]] = false;
}
consider.resize(pnt + 1);
stk.resize(pnt + 1);
lead = d.leader(i * m + j);
i = lead / m, j = lead % m;
in_stk[lead] = true;
stk[pnt] = lead;
pop = false;
break;
} else if (was[nx][ny]) {
ok = false;
break;
} else {
consider.push_back(vector{nx * m + ny});
stk.push_back(nx * m + ny);
i = nx, j = ny;
was[i][j] = true;
in_stk[i * m + j] = true;
pop = false;
break;
}
}
}
}
if (!ok) {
break;
}
if (pop) {
consider.back().pop_back();
}
}
int lead = d.leader(i * m + j);
if (ok) {
int now = d.subtree[lead].size();
if (ans > now) {
ans = now;
cnt = now;
} else if (ans == now) {
cnt += now;
}
}
for (int aa : stk) {
in_stk[aa] = false;
}
}
}
cout << ans << '\n' << cnt << '\n';
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:169:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int p = pnt + 1; p < consider.size(); ++p) {
| ~~^~~~~~~~~~~~~~~~~
virus.cpp:179:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | for (int p = pnt; p < stk.size(); ++p) {
| ~~^~~~~~~~~~~~
virus.cpp:183:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
183 | for (int p = pnt; p < consider.size(); ++p) {
| ~~^~~~~~~~~~~~~~~~~
virus.cpp:191:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int aa = pnt; aa < consider.size() - 1; ++aa) {
| ~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:195:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int aa = pnt; aa < stk.size(); ++aa) {
| ~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
215 ms |
45132 KB |
Output is correct |
| 3 |
Correct |
169 ms |
45080 KB |
Output is correct |
| 4 |
Correct |
198 ms |
45004 KB |
Output is correct |
| 5 |
Correct |
205 ms |
45016 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
364 ms |
48808 KB |
Output is correct |
| 8 |
Correct |
90 ms |
18380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
4 ms |
852 KB |
Output is correct |
| 3 |
Correct |
14 ms |
852 KB |
Output is correct |
| 4 |
Correct |
4 ms |
852 KB |
Output is correct |
| 5 |
Correct |
14 ms |
852 KB |
Output is correct |
| 6 |
Correct |
15 ms |
1108 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
14 ms |
852 KB |
Output is correct |
| 9 |
Correct |
1 ms |
468 KB |
Output is correct |
| 10 |
Correct |
4 ms |
852 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| 13 |
Correct |
13 ms |
944 KB |
Output is correct |
| 14 |
Correct |
15 ms |
980 KB |
Output is correct |
| 15 |
Correct |
14 ms |
948 KB |
Output is correct |
| 16 |
Correct |
14 ms |
980 KB |
Output is correct |
| 17 |
Correct |
8 ms |
724 KB |
Output is correct |
| 18 |
Correct |
2 ms |
468 KB |
Output is correct |
| 19 |
Correct |
15 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
215 ms |
45132 KB |
Output is correct |
| 3 |
Correct |
169 ms |
45080 KB |
Output is correct |
| 4 |
Correct |
198 ms |
45004 KB |
Output is correct |
| 5 |
Correct |
205 ms |
45016 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
364 ms |
48808 KB |
Output is correct |
| 8 |
Correct |
90 ms |
18380 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
4 ms |
852 KB |
Output is correct |
| 11 |
Correct |
14 ms |
852 KB |
Output is correct |
| 12 |
Correct |
4 ms |
852 KB |
Output is correct |
| 13 |
Correct |
14 ms |
852 KB |
Output is correct |
| 14 |
Correct |
15 ms |
1108 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
14 ms |
852 KB |
Output is correct |
| 17 |
Correct |
1 ms |
468 KB |
Output is correct |
| 18 |
Correct |
4 ms |
852 KB |
Output is correct |
| 19 |
Correct |
2 ms |
468 KB |
Output is correct |
| 20 |
Correct |
2 ms |
596 KB |
Output is correct |
| 21 |
Correct |
13 ms |
944 KB |
Output is correct |
| 22 |
Correct |
15 ms |
980 KB |
Output is correct |
| 23 |
Correct |
14 ms |
948 KB |
Output is correct |
| 24 |
Correct |
14 ms |
980 KB |
Output is correct |
| 25 |
Correct |
8 ms |
724 KB |
Output is correct |
| 26 |
Correct |
2 ms |
468 KB |
Output is correct |
| 27 |
Correct |
15 ms |
980 KB |
Output is correct |
| 28 |
Correct |
300 ms |
56132 KB |
Output is correct |
| 29 |
Correct |
174 ms |
45608 KB |
Output is correct |
| 30 |
Correct |
171 ms |
45588 KB |
Output is correct |
| 31 |
Correct |
261 ms |
46124 KB |
Output is correct |
| 32 |
Correct |
253 ms |
46780 KB |
Output is correct |
| 33 |
Correct |
207 ms |
44964 KB |
Output is correct |
| 34 |
Correct |
344 ms |
56516 KB |
Output is correct |
| 35 |
Correct |
226 ms |
40828 KB |
Output is correct |
| 36 |
Correct |
327 ms |
48636 KB |
Output is correct |
| 37 |
Correct |
297 ms |
51472 KB |
Output is correct |
| 38 |
Correct |
275 ms |
55508 KB |
Output is correct |
| 39 |
Correct |
290 ms |
45552 KB |
Output is correct |
| 40 |
Correct |
339 ms |
45596 KB |
Output is correct |
| 41 |
Correct |
163 ms |
45388 KB |
Output is correct |
| 42 |
Correct |
318 ms |
48468 KB |
Output is correct |
| 43 |
Correct |
180 ms |
45472 KB |
Output is correct |
| 44 |
Correct |
94 ms |
18416 KB |
Output is correct |
