| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 147438 | username | Virus Experiment (JOI19_virus) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
char D[200000];
int U[800][800];
int tt[16];
int parent[640000];
int find(int n) {
if (parent[n] != n) parent[n] = find(parent[n]);
return parent[n];
}
int done[640000];
queue<pii> Q;
int visited[800][800];
int main() {
int i,j;
int M,R,C;
scanf("%d %d %d",&M,&R,&C);
for (i = 0; i < M; i++) scanf(" %c",&D[i]),D[i+M] = D[i];
for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) scanf("%d",&U[i][j]);
}
for (i = 1; i < 16; i++) {
int p = -1;
for (j = 0; j < 2*M; j++) {
int yes;
if (D[j] == 'W') yes = (i & 1);
else if (D[j] == 'N') yes = (i & 2);
else if (D[j] == 'E') yes = (i & 4);
else yes = (i & 8);
if (yes) tt[i] = max(tt[i],j-p);
else p = j;
}
if (tt[i] >= M) tt[i] = 100001;
}
int k,l,f = 1,t = 0;
int best = R*C+1,num = 1;
for (i = 0; i < R*C; i++) parent[i] = i;
while (f) {
f = 0;
for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) {
if ((U[i][j] > 0) && !done[i*C+j] && (find(i*C+j) == i*C+j)) {
int c = 0,mx = -1,my = -1;
visited[i][j] = ++t,Q.push(mp(i,j));
while (!Q.empty()) {
int x = Q.front().second,y = Q.front().first;
Q.pop(),c++;
for (k = 0; k < 4; k++) {
int xx = x+dx[k],yy = y+dy[k];
if ((xx >= 0) && (xx < C) && (yy >= 0) && (yy < R) && (visited[yy][xx] != t) && (U[yy][xx] > 0)) {
int m = 0;
for (l = 0; l < 4; l++) {
int x2 = xx+dx[l],y2 = yy+dy[l];
if ((x2 >= 0) && (x2 < C) && (y2 >= 0) && (y2 < R) && (visited[y2][x2] == t)) m |= (1 << l);
}
if (tt[m] >= U[yy][xx]) {
if (find(yy*C+xx) != i*C+j) mx = xx,my = yy;
visited[yy][xx] = t;
Q.push(mp(yy,xx));
if(mx != -1)break;
}
}
}
if (mx != -1) break;
}
while (!Q.empty()) Q.pop();
if (mx == -1) {
if (c < best) best = num = c;
else if (c == best) num += c;
done[i*C+j] = 1;
}
// else if (done[find(my*C+mx)]) done[i*C+j] = 1;
else parent[i*C+j] = find(my*C+mx);
f = 1;
}
}
}
}
printf("%d\n%d\n",best,num);
return 0;
}