This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
const int MN = 402;
int E = 1;
int la[MN * MN * 4], nxt[MN * MN * 4], oppo[MN * MN * 4], deg[MN * MN * 2];
void add(int u, int v) {
nxt[E] = la[u];
la[u] = E;
oppo[E] = v;
deg[v]++;
E++;
}
int N, M;
char G[MN][MN];
int f(int r, int c, int t) {
return r * (2 * M) + c * 2 + t;
}
int ans[MN * MN * 2], vis[MN * MN * 2], pos = 1;
int q[1000010], head, tail;
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
getchar();
for(int j = 0; j < M; j++) {
G[i][j] = getchar();
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
for(int k = 0; k < 2; k++) {
if(k) {
if(i) add(f(i - 1, j, k), f(i, j, k));
}
else if(i < N - 1) add(f(i + 1, j, k), f(i, j, k));
if(k ^ (G[i][j] == 'N')) {
if(j) add(f(i, j - 1, G[i][j - 1] == 'Z'), f(i, j, k));
}
else if(j < M - 1) add(f(i, j + 1, G[i][j + 1] == 'N'), f(i, j, k));
}
}
}
head = tail = 0;
for(int i = 0; i < N * M * 2; i++) if(!deg[i]) {
q[tail++] = i;
}
while(head < tail) {
int u = q[head++];
for(int i = la[u]; i; i = nxt[i]) {
int v = oppo[i];
deg[v]--;
if(!deg[v]) {
q[tail++] = v;
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int k = G[i][j] == 'N';
if(deg[ f(i, j, k) ]) continue;
head = tail = 0;
q[tail++] = f(i, j, k);
ans[ f(i, j, k) ] += M - j;
vis[ f(i, j, k) ] = pos;
while(head < tail) {
int u = q[head++];
if(!la[u]) continue;
for(int x = la[u];; x = nxt[x]) {
int v = oppo[x];
if(vis[v] != pos && deg[v] == 0) {
q[tail++] = v;
ans[v] += M - j;
vis[v] = pos;
}
if(nxt[x] == 0) break;
}
}
}
pos++;
}
for(int i = 0; i < N; i++) {
for(int j = M - 1; j >= 0; j--) {
int k = G[i][j] == 'Z';
if(deg[ f(i, j, k) ]) continue;
head = tail = 0;
q[tail++] = f(i, j, k);
ans[ f(i, j, k) ] += j + 1;
vis[ f(i, j, k) ] = pos;
while(head < tail) {
int u = q[head++];
if(!la[u]) continue;
for(int x = la[u];; x = nxt[x]) {
int v = oppo[x];
if(vis[v] != pos && deg[v] == 0) {
q[tail++] = v;
ans[v] += j + 1;
vis[v] = pos;
}
if(nxt[x] == 0) break;
}
}
}
pos++;
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(deg[ f(i, j, 0) ] && deg[ f(i, j, 1) ]) printf("-1 ");
else if(deg[ f(i, j, 0) ]) printf("%d ", 2 * ans[ f(i, j, 1) ]);
else if(deg[ f(i, j, 1) ]) printf("%d ", 2 * ans[ f(i, j, 0) ]);
else printf("%d ", 2 * min(ans[ f(i, j, 0) ], ans[ f(i, j, 1) ]));
}
printf("\n");
}
}
Compilation message (stderr)
sandwich.cpp: In function 'int main()':
sandwich.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |