#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int N = 707070;
const int INF = 1e9 + 10;
int n, m, len, a[N], limit[1 << 4]; string s;
int encode(char c) {
if (c == 'S')
return 0;
else if (c == 'E')
return 1;
else if (c == 'N')
return 2;
else
return 3;
}
int f(int x, int y) {
return m * (x - 1) + (y - 1) + 1;
}
pair<int, int> g(int x) {
return { (x - 1) / m + 1, (x - 1) % m + 1 };
}
bool in(int x, int y) {
return (1 <= x && x <= n && 1 <= y && y <= m);
}
int par[N], anc[N], vis[N];
vector<int> cell[N], adj[N];
bool bad[N];
int Find(int a) {
return par[a] = (par[a] == a) ? a : Find(par[a]);
}
bool ok(int v, int r) { // check if cell v is reachable from component r
auto [x, y] = g(v);
if (!in(x, y) || a[v] == 0 || Find(v) == r)
return false;
int msk = 0;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && a[w] && Find(w) == r)
msk |= 1 << t;
}
return a[v] <= limit[msk];
}
void Union(int a, int b) {
a = Find(a); b = Find(b);
if (a != b) {
if (cell[a].size() < cell[b].size()) {
swap(a, b);
anc[a] = anc[b];
}
par[b] = a;
for (int v : cell[b]) {
cell[a].push_back(v);
auto [x, y] = g(v);
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && ok(w, a))
adj[a].push_back(w);
}
}
vector<int>().swap(cell[b]);
vector<int>().swap(adj[b]);
}
}
bool dfs(int v) {
auto [x, y] = g(v);
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
int w = f(nx, ny);
if (in(nx, ny) && ok(w, v))
adj[v].push_back(w);
}
int s = Find(v);
while (!adj[s].empty()) {
int z = adj[s].back();
adj[s].pop_back();
if (!ok(z, s))
continue;
if (vis[z] == 0) {
vis[z] = 1;
anc[z] = s;
bool f = dfs(z);
if (!f) {
vis[v] = 2;
bad[s] = 1;
return false;
}
}
else if (vis[z] == 1) {
while (Find(s) != Find(z)) {
Union(anc[s], s);
s = Find(s);
}
}
else {
vis[v] = 2;
bad[s] = 1;
return false;
}
s = Find(v);
}
vis[v] = 2;
return true;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> len >> n >> m >> s;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[f(i, j)];
// upper bound for each direction set
s += s;
for (int msk = 0; msk < (1 << 4); msk++) {
int cnt = 0, maxv = 0;
for (int i = 0; i < 2 * len; i++) {
if (msk >> encode(s[i]) & 1)
++cnt;
else {
maxv = max(maxv, cnt);
cnt = 0;
}
}
maxv = max(maxv, cnt);
if (cnt == 2 * len)
limit[msk] = INF;
else
limit[msk] = maxv;
}
for (int i = 1; i <= n * m; i++) {
par[i] = i;
cell[i].push_back(i);
}
for (int i = 1; i <= n * m; i++) {
if (a[i] && !vis[i]) {
vis[i] = 1;
dfs(i);
}
}
for (int i = 1; i <= n * m; i++)
if (a[i] && Find(i) == i)
bad[anc[i]] = 1;
map<int, int> mp;
for (int i = 1; i <= n * m; i++)
if (a[i] && Find(i) == i && !bad[i])
mp[cell[i].size()] += cell[i].size();
cout << mp.begin()->first << '\n';
cout << mp.begin()->second << '\n';
}
Compilation message
virus.cpp: In function 'bool ok(int, int)':
virus.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | auto [x, y] = g(v);
| ^
virus.cpp: In function 'void Union(int, int)':
virus.cpp:66:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
66 | auto [x, y] = g(v);
| ^
virus.cpp: In function 'bool dfs(int)':
virus.cpp:81:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | auto [x, y] = g(v);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
33748 KB |
Output is correct |
2 |
Correct |
286 ms |
74532 KB |
Output is correct |
3 |
Correct |
257 ms |
84288 KB |
Output is correct |
4 |
Correct |
241 ms |
81612 KB |
Output is correct |
5 |
Correct |
202 ms |
61648 KB |
Output is correct |
6 |
Correct |
17 ms |
33492 KB |
Output is correct |
7 |
Correct |
415 ms |
63852 KB |
Output is correct |
8 |
Correct |
99 ms |
44640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
33556 KB |
Output is correct |
2 |
Correct |
20 ms |
33880 KB |
Output is correct |
3 |
Correct |
37 ms |
33948 KB |
Output is correct |
4 |
Correct |
20 ms |
33956 KB |
Output is correct |
5 |
Correct |
39 ms |
33876 KB |
Output is correct |
6 |
Correct |
38 ms |
34148 KB |
Output is correct |
7 |
Correct |
16 ms |
33552 KB |
Output is correct |
8 |
Correct |
36 ms |
33876 KB |
Output is correct |
9 |
Correct |
18 ms |
33616 KB |
Output is correct |
10 |
Correct |
19 ms |
33932 KB |
Output is correct |
11 |
Correct |
17 ms |
33672 KB |
Output is correct |
12 |
Correct |
18 ms |
33876 KB |
Output is correct |
13 |
Correct |
34 ms |
33912 KB |
Output is correct |
14 |
Correct |
33 ms |
33932 KB |
Output is correct |
15 |
Correct |
35 ms |
34136 KB |
Output is correct |
16 |
Correct |
39 ms |
33892 KB |
Output is correct |
17 |
Correct |
27 ms |
33748 KB |
Output is correct |
18 |
Correct |
18 ms |
33708 KB |
Output is correct |
19 |
Correct |
38 ms |
33932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
33748 KB |
Output is correct |
2 |
Correct |
286 ms |
74532 KB |
Output is correct |
3 |
Correct |
257 ms |
84288 KB |
Output is correct |
4 |
Correct |
241 ms |
81612 KB |
Output is correct |
5 |
Correct |
202 ms |
61648 KB |
Output is correct |
6 |
Correct |
17 ms |
33492 KB |
Output is correct |
7 |
Correct |
415 ms |
63852 KB |
Output is correct |
8 |
Correct |
99 ms |
44640 KB |
Output is correct |
9 |
Correct |
17 ms |
33556 KB |
Output is correct |
10 |
Correct |
20 ms |
33880 KB |
Output is correct |
11 |
Correct |
37 ms |
33948 KB |
Output is correct |
12 |
Correct |
20 ms |
33956 KB |
Output is correct |
13 |
Correct |
39 ms |
33876 KB |
Output is correct |
14 |
Correct |
38 ms |
34148 KB |
Output is correct |
15 |
Correct |
16 ms |
33552 KB |
Output is correct |
16 |
Correct |
36 ms |
33876 KB |
Output is correct |
17 |
Correct |
18 ms |
33616 KB |
Output is correct |
18 |
Correct |
19 ms |
33932 KB |
Output is correct |
19 |
Correct |
17 ms |
33672 KB |
Output is correct |
20 |
Correct |
18 ms |
33876 KB |
Output is correct |
21 |
Correct |
34 ms |
33912 KB |
Output is correct |
22 |
Correct |
33 ms |
33932 KB |
Output is correct |
23 |
Correct |
35 ms |
34136 KB |
Output is correct |
24 |
Correct |
39 ms |
33892 KB |
Output is correct |
25 |
Correct |
27 ms |
33748 KB |
Output is correct |
26 |
Correct |
18 ms |
33708 KB |
Output is correct |
27 |
Correct |
38 ms |
33932 KB |
Output is correct |
28 |
Correct |
570 ms |
124456 KB |
Output is correct |
29 |
Correct |
307 ms |
81948 KB |
Output is correct |
30 |
Correct |
398 ms |
127060 KB |
Output is correct |
31 |
Correct |
447 ms |
63564 KB |
Output is correct |
32 |
Correct |
449 ms |
64104 KB |
Output is correct |
33 |
Correct |
248 ms |
77440 KB |
Output is correct |
34 |
Correct |
585 ms |
127844 KB |
Output is correct |
35 |
Correct |
411 ms |
103244 KB |
Output is correct |
36 |
Correct |
520 ms |
67672 KB |
Output is correct |
37 |
Correct |
505 ms |
89248 KB |
Output is correct |
38 |
Correct |
531 ms |
127956 KB |
Output is correct |
39 |
Correct |
342 ms |
76812 KB |
Output is correct |
40 |
Correct |
392 ms |
71672 KB |
Output is correct |
41 |
Correct |
233 ms |
78280 KB |
Output is correct |
42 |
Correct |
419 ms |
106164 KB |
Output is correct |
43 |
Correct |
313 ms |
83696 KB |
Output is correct |
44 |
Correct |
104 ms |
44700 KB |
Output is correct |