#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
struct Node {
int left, right, inner, len;
};
const int N = 2e5 + 5, Z = 51, INF = 2e9;
string s;
char dir[5] = "WESN";
int m, r, c;
int a[N], resistance[Z][Z], mask[Z][Z], last_ch[Z][Z],
dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
Node tail[Z][Z];
bool infected[Z][Z], rip[Z][Z];
Node operator + (Node a, Node b) {
Node c;
c.len = a.len + b.len;
c.inner = max(a.inner, b.inner);
c.inner = max(c.inner, a.right + b.left);
c.left = a.left + (a.inner == a.len ? b.left : 0);
c.right = b.right + (b.inner == b.len ? a.right : 0);
return c;
}
struct SegTree {
Node t[N * 4];
void build(int v, int L, int R) {
if (L == R) {
t[v] = {a[L], a[L], a[L], 1};
}
else {
int m = (L + R) >> 1;
build(v * 2, L, m);
build(v * 2 + 1, m + 1, R);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
Node getFirstGreaterOrEqual(int x, int y, int v = 1, int L = 0, int R = m + m - 1) {
if (R < x)
return { 0, 0, 0, 0 };
if (L == R)
return t[v].inner >= y ? Node{ L, -1 } : t[v];
if (L >= x && t[v].inner < y)
return t[v];
int m = (L + R) >> 1;
if (x > m)
return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
Node ln = getFirstGreaterOrEqual(x, y, v * 2, L, m);
if (ln.right == -1)
return ln;
if (ln.right + t[v * 2 + 1].left >= y)
return { m + y - ln.right, -1 };
if (t[v * 2 + 1].inner >= y)
return getFirstGreaterOrEqual(x, y, v * 2 + 1, m + 1, R);
return ln + t[v * 2 + 1];
}
Node getSum(int l, int r, int v = 1, int L = 0, int R = m + m - 1) {
if (l > r)
return { 0, 0, 0, 0 };
if (l == L && r == R)
return t[v];
int m = (L + R) >> 1;
return getSum(l, min(m, r), v * 2, L, m) +
getSum(max(m + 1, l), r, v * 2 + 1, m + 1, R);
}
Node que(int l, int r) {
int cur_len = r - l + 1;
if (t[1].inner == t[1].len)
return { cur_len, cur_len, cur_len, cur_len };
if (cur_len >= m)
l = r - m + 2;
if (l > r)
return { 0, 0, 0, 0 };
r %= m;
l %= m;
if (l > r)
r += m;
return getSum(l, r);
}
} t[1 << 4];
struct Event {
int t, x, y;
bool operator < (const Event &oth) const {
return t > oth.t;
}
};
priority_queue<Event> pq;
int infected_count = 0;
void eventHappens(Event e) {
if (infected[e.x][e.y])
return;
infected[e.x][e.y] = 1;
infected_count++;
for (int i = 0; i < 4; i++) {
int p = e.x + dx[i],
q = e.y + dy[i];
if (p >= 0 && p < r && q >= 0 && q < c &&
!infected[p][q] && resistance[p][q] != 0 && !rip[p][q]) {
mask[p][q] |= 1 << i;
tail[p][q] = tail[p][q] + t[mask[p][q]].que(last_ch[p][q] + 1, e.t);
last_ch[p][q] = e.t;
int new_expected_time = INF, rest = resistance[p][q] - tail[p][q].right;
if (t[mask[p][q]].t[1].inner == m + m) {
new_expected_time = e.t + rest;
rip[p][q] = 1;
}
else {
Node node = t[mask[p][q]].getSum((e.t + 1) % m, m + m - 1);
if (node.left >= rest) {
new_expected_time = e.t + rest;
rip[p][q] = 1;
}
else {
node = t[mask[p][q]].getFirstGreaterOrEqual((e.t + 1) % m, resistance[p][q]);
if (node.right == -1)
new_expected_time = node.left - (e.t + 1) % m + 1 + e.t;
}
}
if (new_expected_time != INF)
pq.push({ new_expected_time, p, q });
}
}
}
int mn = INF, ct = 0;
void handle(int i, int j) {
for (int x = 0; x < r; x++) {
for (int y = 0; y < c; y++) {
mask[x][y] = 0;
last_ch[x][y] = -1;
tail[x][y] = { 0, 0, 0, 0 };
infected[x][y] = 0;
rip[x][y] = 0;
}
}
infected_count = 0;
pq.push({ -1, i, j });
while (!pq.empty()) {
Event e = pq.top();
pq.pop();
eventHappens(e);
if (infected_count > mn)
break;
}
pq = priority_queue<Event>();
}
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> r >> c >> s;
for (char &c : s) {
c = find(dir, dir + 4, c) - dir;
}
s += s;
for (int i = 0; i < (1 << 4); i++) {
for (int j = 0; j < m + m; j++) {
a[j] = (i >> s[j]) & 1;
}
t[i].build(1, 0, m + m - 1);
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> resistance[i][j];
}
}
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (resistance[i][j] != 0) {
handle(i, j);
if (infected_count < mn) {
mn = infected_count;
ct = 0;
}
if (infected_count == mn)
ct++;
}
}
}
cout << mn << "\n" << ct;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
66812 KB |
Output is correct |
| 2 |
Runtime error |
292 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
154 ms |
133028 KB |
Output is correct |
| 3 |
Correct |
158 ms |
133024 KB |
Output is correct |
| 4 |
Correct |
153 ms |
132992 KB |
Output is correct |
| 5 |
Correct |
152 ms |
132952 KB |
Output is correct |
| 6 |
Execution timed out |
2062 ms |
132948 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
66812 KB |
Output is correct |
| 2 |
Runtime error |
292 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
