#include <bits/stdc++.h>
using namespace std;
#define count cnt
string s;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dir[] = {'E', 'W', 'S', 'N'};
typedef pair <int, int> pii;
bool done[805][805];
bool vis[805][805];
bool infect[1 << 4][805][805];
int a[805][805];
int ans[805][805];
int optimal;
int count;
int r, c;
unordered_set <int> reachable[805][805];
namespace DSU {
int p[805 * 805];
int s[805 * 805];
int init(int n) {
iota(p,p + n,0);
fill(s,s + n,1);
return 1;
}
int lead(int x) {
return p[x] == x ? x : p[x] = lead(p[x]);
}
int join(int x,int y) {
x = lead(x);
y = lead(y);
p[x] = y;
return 1;
}
}
inline int convert(int i, int j) {
return j + i * c;
}
inline int valid(int x,int y) {
if (x < 0 || x >= r) return 0;
if (y < 0 || y >= c) return 0;
return 1;
}
inline int check(int x,int y) {
int mask = 0;
for(int i = 0 ; i < 4 ; ++i) {
int xx = x + dx[i];
int yy = y + dy[i];
if (valid(xx,yy) && vis[xx][yy])
mask |= (1 << i);
}
return infect[mask][x][y];
}
void solve(int x, int y) {
queue <pii> Q;
vector <pii> reach;
vis[x][y] = true;
Q.push(pii(x, y));
bool bad = false;
while(!Q.empty()) {
int p = Q.front().first;
int q = Q.front().second;
Q.pop();
reach.push_back(pii(p, q));
if(bad) continue;
for(int i = 0; i < 4; i++) {
int nx = p + dx[i];
int ny = q + dy[i];
if(!valid(nx, ny) || vis[nx][ny]) continue;
if(check(nx, ny)) {
int anc = DSU::lead(convert(nx, ny));
nx = (anc / c);
ny = (anc % c);
if(done[nx][ny]) {
if(ans[nx][ny] == optimal && reachable[nx][ny].find(convert(x, y)) != reachable[nx][ny].end()) {
++count;
ans[x][y] = ans[nx][ny];
DSU::join(convert(x, y), anc);
} else {
ans[x][y] = INT_MAX;
}
bad = true;
break;
}
Q.push(pii(nx, ny));
vis[nx][ny] = true;
}
}
}
for(auto i : reach) {
vis[i.first][i.second] = false;
}
done[x][y] = true;
if(!bad) {
ans[x][y] = reach.size();
if(optimal == ans[x][y]) {
++count;
} else if (ans[x][y] < optimal) {
optimal = ans[x][y];
count = 1;
}
reachable[x][y].max_load_factor(0.25); //updated !
for(auto i : reach) {
reachable[x][y].insert(convert(i.first, i.second));
}
}
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n >> r >> c;
cin >> s;
s += s;
for(int x = 0; x < r; x++) {
for(int y = 0; y < c; y++) {
cin >> a[x][y];
}
}
for(int m = 0 ; m < 16 ; ++m) {
int opt = 0;
int cur = 0;
for(char c : s) {
bool have = 0;
for(int i = 0 ; i < 4 ; ++i) if (m >> i & 1)
if (c == dir[i]) {
have = 1;
break;
}
if (have) cur++;
else cur = 0;
opt = max(cur,opt);
}
if (opt == n + n)
opt = INT_MAX;
for(int i = 0 ; i < r ; ++i)
for(int j = 0 ; j < c ; ++j)
if (a[i][j] && a[i][j] <= opt)
infect[m][i][j] = 1;
}
optimal = INT_MAX;
count = 0;
DSU::init(r * c);
for(int i = 0 ; i < r ; ++i)
for(int j = 0 ; j < c ; ++j) if (a[i][j])
solve(i,j);
cout << optimal << endl;
cout << count << endl;
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:158:37: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
for(int j = 0 ; j < c ; ++j) if (a[i][j])
^~
virus.cpp:161:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
cout << optimal << endl;
^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
36216 KB |
Output is correct |
2 |
Correct |
727 ms |
177640 KB |
Output is correct |
3 |
Runtime error |
772 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
36144 KB |
Output is correct |
2 |
Correct |
50 ms |
36316 KB |
Output is correct |
3 |
Correct |
70 ms |
36512 KB |
Output is correct |
4 |
Correct |
46 ms |
36508 KB |
Output is correct |
5 |
Correct |
69 ms |
36344 KB |
Output is correct |
6 |
Correct |
72 ms |
37532 KB |
Output is correct |
7 |
Correct |
37 ms |
36088 KB |
Output is correct |
8 |
Correct |
71 ms |
37376 KB |
Output is correct |
9 |
Correct |
40 ms |
37112 KB |
Output is correct |
10 |
Correct |
48 ms |
36508 KB |
Output is correct |
11 |
Correct |
39 ms |
36856 KB |
Output is correct |
12 |
Correct |
40 ms |
37316 KB |
Output is correct |
13 |
Correct |
87 ms |
42140 KB |
Output is correct |
14 |
Correct |
87 ms |
42272 KB |
Output is correct |
15 |
Correct |
77 ms |
42396 KB |
Output is correct |
16 |
Correct |
69 ms |
37404 KB |
Output is correct |
17 |
Correct |
57 ms |
37240 KB |
Output is correct |
18 |
Correct |
41 ms |
37112 KB |
Output is correct |
19 |
Correct |
72 ms |
37004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
36216 KB |
Output is correct |
2 |
Correct |
727 ms |
177640 KB |
Output is correct |
3 |
Runtime error |
772 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
4 |
Halted |
0 ms |
0 KB |
- |