#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 100'010;
const int M = 810;
int mx[16];
int val[M][M];
int n, m, d;
string s;
pii constexpr dir[] = {
{-1, 0},
{0, -1},
{1, 0},
{0, 1},
};
bool isin(int i, int j) { return 0 <= i && i < n && 0 <= j && j < m; }
namespace dsu {
struct comp {
vector<pii> nodes;
vector<pii> adj;
comp *par;
int col;
int dfsvis;
bool bad;
} comps[M][M];
int cmpcol[M][M];
void add(comp *c, int i, int j) {
if (val[i][j] == 0)
return;
int msk = 0;
Loop (k,0,4) {
auto [x, y] = dir[k];
if (isin(i+x, j+y) && cmpcol[i+x][j+y] == c->col)
msk ^= (1 << k);
}
if (mx[msk] >= val[i][j])
c->adj.emplace_back(i, j);
}
void addadj(comp *c, int i, int j) {
Loop (k,0,4) {
auto [x, y] = dir[k];
if (isin(i+x, j+y))
add(c, i+x, j+y);
}
}
comp *rt(comp *c) { return c->par? (c->par = rt(c->par)): c; }
void unite(comp *v, comp *u) {
v = rt(v);
u = rt(u);
assert(v != u);
if (v->nodes.size() < u->nodes.size())
swap(v, u);
v->nodes.insert(v->nodes.end(), u->nodes.begin(), u->nodes.end());
for (auto [i, j] : u->nodes)
cmpcol[i][j] = v->col;
for (auto [i, j] : u->nodes)
addadj(v, i, j);
vector<pii>().swap(u->nodes);
vector<pii>().swap(u->adj);
u->par = v;
}
comp *rt(int i, int j) { return rt(&comps[i][j]); }
comp *rt(pii p) { return rt(&comps[p.first][p.second]); }
void init() {
int cnt = 0;
Loop (i,0,n) Loop (j,0,m) {
if (val[i][j] == 0)
continue;
comp *v = &comps[i][j];
v->par = 0;
v->col = ++cnt;
cmpcol[i][j] = v->col;
v->nodes = {pii{i, j}};
v->dfsvis = 0;
v->bad = 0;
addadj(v, i, j);
}
}
}
void mkmx()
{
int msk[256];
msk['N'] = 1<<0;
msk['W'] = 1<<1;
msk['S'] = 1<<2;
msk['E'] = 1<<3;
Loop (dard,0,16) {
int lst = 0;
Loop (i,0,2*d) {
int x = msk[s[i>=d?i-d:i]];
if (!(dard & x)) {
mx[dard] = max<int>(mx[dard], i-lst);
lst = i+1;
}
}
mx[dard] = max<int>(mx[dard], 2*d-lst);
}
}
void dfs(dsu::comp *c, int t)
{
vector<dsu::comp *> st = {c};
c->dfsvis = t;
for (;;) {
auto v = st.back();
if (v->adj.empty()) {
st.pop_back();
break;
}
auto u = dsu::rt(v->adj.back());
v->adj.pop_back();
if (v == u)
continue;
if (u->dfsvis && u->dfsvis != t)
break;
if (u->dfsvis == t) {
while (st.back() != dsu::rt(u)) {
auto x = st.back(); st.pop_back();
auto y = st.back(); st.pop_back();
dsu::unite(x, y);
st.push_back(dsu::rt(x));
}
} else {
st.push_back(u);
u->dfsvis = t;
}
}
for (auto v : st)
v->bad = 1;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> d >> n >> m >> s;
Loop (i,0,n) Loop (j,0,m) {
cin >> val[i][j];
val[i][j] = min(val[i][j], d);
}
mkmx();
dsu::init();
int cnt = 0;
Loop (i,0,n) Loop (j,0,m) {
if (val[i][j] == 0)
continue;
auto c = dsu::rt(i, j);
if (c->dfsvis)
continue;
dfs(c, ++cnt);
}
int ans = 1e9, ansc = 0;
Loop (i,0,n) Loop (j,0,m) {
if (val[i][j] == 0)
continue;
auto c = dsu::rt(i, j);
if (c->bad)
continue;
if (ans > c->nodes.size()) {
ans = c->nodes.size();
ansc = 0;
}
if (ans == c->nodes.size())
++ansc;
}
cout << ans << '\n' << ansc << '\n';
}
Compilation message
virus.cpp: In function 'void mkmx()':
virus.cpp:102:29: warning: array subscript has type 'char' [-Wchar-subscripts]
102 | int x = msk[s[i>=d?i-d:i]];
| ^
virus.cpp: In function 'int main()':
virus.cpp:170:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
170 | if (ans > c->nodes.size()) {
| ~~~~^~~~~~~~~~~~~~~~~
virus.cpp:174:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | if (ans == c->nodes.size())
| ~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46676 KB |
Output is correct |
2 |
Correct |
141 ms |
84480 KB |
Output is correct |
3 |
Correct |
139 ms |
91560 KB |
Output is correct |
4 |
Correct |
129 ms |
91580 KB |
Output is correct |
5 |
Correct |
118 ms |
71544 KB |
Output is correct |
6 |
Correct |
21 ms |
50516 KB |
Output is correct |
7 |
Correct |
204 ms |
91804 KB |
Output is correct |
8 |
Correct |
71 ms |
56920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46616 KB |
Output is correct |
2 |
Correct |
25 ms |
46804 KB |
Output is correct |
3 |
Correct |
34 ms |
46788 KB |
Output is correct |
4 |
Correct |
23 ms |
46804 KB |
Output is correct |
5 |
Correct |
34 ms |
46748 KB |
Output is correct |
6 |
Correct |
35 ms |
47180 KB |
Output is correct |
7 |
Correct |
20 ms |
46548 KB |
Output is correct |
8 |
Correct |
34 ms |
47044 KB |
Output is correct |
9 |
Correct |
22 ms |
46992 KB |
Output is correct |
10 |
Correct |
25 ms |
46804 KB |
Output is correct |
11 |
Correct |
22 ms |
46988 KB |
Output is correct |
12 |
Correct |
28 ms |
47072 KB |
Output is correct |
13 |
Correct |
35 ms |
47060 KB |
Output is correct |
14 |
Correct |
37 ms |
47040 KB |
Output is correct |
15 |
Correct |
32 ms |
47116 KB |
Output is correct |
16 |
Correct |
40 ms |
47052 KB |
Output is correct |
17 |
Correct |
27 ms |
47048 KB |
Output is correct |
18 |
Correct |
22 ms |
47024 KB |
Output is correct |
19 |
Correct |
34 ms |
47028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
46676 KB |
Output is correct |
2 |
Correct |
141 ms |
84480 KB |
Output is correct |
3 |
Correct |
139 ms |
91560 KB |
Output is correct |
4 |
Correct |
129 ms |
91580 KB |
Output is correct |
5 |
Correct |
118 ms |
71544 KB |
Output is correct |
6 |
Correct |
21 ms |
50516 KB |
Output is correct |
7 |
Correct |
204 ms |
91804 KB |
Output is correct |
8 |
Correct |
71 ms |
56920 KB |
Output is correct |
9 |
Correct |
20 ms |
46616 KB |
Output is correct |
10 |
Correct |
25 ms |
46804 KB |
Output is correct |
11 |
Correct |
34 ms |
46788 KB |
Output is correct |
12 |
Correct |
23 ms |
46804 KB |
Output is correct |
13 |
Correct |
34 ms |
46748 KB |
Output is correct |
14 |
Correct |
35 ms |
47180 KB |
Output is correct |
15 |
Correct |
20 ms |
46548 KB |
Output is correct |
16 |
Correct |
34 ms |
47044 KB |
Output is correct |
17 |
Correct |
22 ms |
46992 KB |
Output is correct |
18 |
Correct |
25 ms |
46804 KB |
Output is correct |
19 |
Correct |
22 ms |
46988 KB |
Output is correct |
20 |
Correct |
28 ms |
47072 KB |
Output is correct |
21 |
Correct |
35 ms |
47060 KB |
Output is correct |
22 |
Correct |
37 ms |
47040 KB |
Output is correct |
23 |
Correct |
32 ms |
47116 KB |
Output is correct |
24 |
Correct |
40 ms |
47052 KB |
Output is correct |
25 |
Correct |
27 ms |
47048 KB |
Output is correct |
26 |
Correct |
22 ms |
47024 KB |
Output is correct |
27 |
Correct |
34 ms |
47028 KB |
Output is correct |
28 |
Correct |
263 ms |
110020 KB |
Output is correct |
29 |
Correct |
259 ms |
107848 KB |
Output is correct |
30 |
Correct |
205 ms |
102144 KB |
Output is correct |
31 |
Correct |
294 ms |
98024 KB |
Output is correct |
32 |
Correct |
246 ms |
99140 KB |
Output is correct |
33 |
Correct |
133 ms |
88780 KB |
Output is correct |
34 |
Correct |
367 ms |
131212 KB |
Output is correct |
35 |
Correct |
242 ms |
101380 KB |
Output is correct |
36 |
Correct |
322 ms |
111896 KB |
Output is correct |
37 |
Correct |
344 ms |
112316 KB |
Output is correct |
38 |
Correct |
264 ms |
125116 KB |
Output is correct |
39 |
Correct |
243 ms |
94232 KB |
Output is correct |
40 |
Correct |
289 ms |
95184 KB |
Output is correct |
41 |
Correct |
171 ms |
87752 KB |
Output is correct |
42 |
Correct |
295 ms |
93516 KB |
Output is correct |
43 |
Correct |
208 ms |
99952 KB |
Output is correct |
44 |
Correct |
75 ms |
58368 KB |
Output is correct |