#include<bits/stdc++.h>
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];
void add(int u, int v) {
nxt[E] = la[u];
la[u] = E;
oppo[E] = v;
E++;
}
int N, M;
char G[MN][MN];
vector<int> sadj[MN * MN * 2];
int tin[MN * MN * 2], bck[MN * MN * 2], id[MN * MN * 2], sz[MN * MN * 2], timer = 1, scnt = 1;
stack<int> stk;
inline int f(int r, int c, int t) {
return r * (2 * M) + c * 2 + t;
}
void dfs(int u) {
tin[u] = timer++;
bck[u] = tin[u];
stk.push(u);
for(int i = la[u]; i; i = nxt[i]) {
int v = oppo[i];
if(!tin[v]) {
dfs(v);
bck[u] = min(bck[u], bck[v]);
}
else if(!id[v]) {
bck[u] = min(bck[u], tin[v]);
}
}
if(bck[u] == tin[u]) {
while(1) {
int t = stk.top(); stk.pop();
id[t] = scnt;
if(t == u) break;
}
scnt++;
}
}
int del[MN * MN * 2], chk[MN * MN * 2];
queue<int> q;
void scc() {
for(int i = 0; i < N * M * 2; i++) if(!tin[i]) {
dfs(i);
}
for(int i = 0; i < N * M * 2; i++) {
sz[ id[i] ]++;
for(int j = la[i]; j; j = nxt[j]) {
int k = oppo[j];
if(id[i] == id[k]) continue;
sadj[ id[i] ].push_back(id[k]);
}
}
for(int i = 0; i < scnt; i++) {
if(sz[i] > 1) {
q.push(i);
del[i] = 1;
}
}
while(!q.empty()) {
int u = q.front(); q.pop();
for(int i = 0; i < sadj[u].size(); i++) {
int v = sadj[u][i];
if(!del[v]) {
q.push(v);
del[v] = 1;
}
}
}
for(int i = 0; i < N * M * 2; i++) {
chk[i] = del[ id[i] ];
}
}
int ans[MN * MN * 2];
bool vis[MN * MN * 2];
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < N; i++) {
scanf("\n");
for(int j = 0; j < M; j++) {
scanf("%c", &G[i][j]);
}
}
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));
}
}
}
scc();
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) for(int k = 0; k < M; k++) for(int a = 0; a < 2; a++) vis[ j * (2 * M) + k * 2 + a ] = 0;
for(int j = 0; j < M; j++) {
int k = G[i][j] == 'N';
if(chk[ f(i, j, k) ]) continue;
q.push(f(i, j, k));
ans[ f(i, j, k) ] += M - j;
vis[ f(i, j, k) ] = true;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int x = la[u]; x != 0; x = nxt[x]) {
int v = oppo[x];
if(!chk[v] && !vis[v]) {
q.push(v);
ans[v] += M - j;
vis[v] = true;
}
}
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) for(int k = 0; k < M; k++) for(int a = 0; a < 2; a++) vis[ j * (2 * M) + k * 2 + a ] = 0;
for(int j = M - 1; j >= 0; j--) {
int k = G[i][j] == 'Z';
if(chk[ f(i, j, k) ]) continue;
q.push(f(i, j, k));
ans[ f(i, j, k) ] += j + 1;
vis[ f(i, j, k) ] = true;
while(!q.empty()) {
int u = q.front(); q.pop();
for(int x = la[u]; x != 0; x = nxt[x]) {
int v = oppo[x];
if(!chk[v] && !vis[v]) {
q.push(v);
ans[v] += j + 1;
vis[v] = true;
}
}
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(chk[ f(i, j, 0) ] && chk[ f(i, j, 1) ]) printf("-1 ");
else if(chk[ f(i, j, 0) ]) printf("%d ", 2 * ans[ f(i, j, 1) ]);
else if(chk[ 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
sandwich.cpp: In function 'void scc()':
sandwich.cpp:77:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < sadj[u].size(); i++) {
~~^~~~~~~~~~~~~~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
~~~~~^~~~~~
sandwich.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &G[i][j]);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7928 KB |
Output is correct |
2 |
Correct |
10 ms |
8168 KB |
Output is correct |
3 |
Correct |
8 ms |
8168 KB |
Output is correct |
4 |
Correct |
8 ms |
8168 KB |
Output is correct |
5 |
Correct |
10 ms |
8168 KB |
Output is correct |
6 |
Correct |
9 ms |
8576 KB |
Output is correct |
7 |
Correct |
15 ms |
8576 KB |
Output is correct |
8 |
Correct |
15 ms |
8592 KB |
Output is correct |
9 |
Correct |
15 ms |
8608 KB |
Output is correct |
10 |
Correct |
21 ms |
8624 KB |
Output is correct |
11 |
Correct |
20 ms |
8624 KB |
Output is correct |
12 |
Correct |
13 ms |
8624 KB |
Output is correct |
13 |
Correct |
19 ms |
8640 KB |
Output is correct |
14 |
Correct |
16 ms |
8768 KB |
Output is correct |
15 |
Correct |
17 ms |
8768 KB |
Output is correct |
16 |
Correct |
15 ms |
8768 KB |
Output is correct |
17 |
Correct |
15 ms |
8768 KB |
Output is correct |
18 |
Correct |
16 ms |
8768 KB |
Output is correct |
19 |
Correct |
14 ms |
8768 KB |
Output is correct |
20 |
Correct |
14 ms |
8768 KB |
Output is correct |
21 |
Correct |
12 ms |
8868 KB |
Output is correct |
22 |
Correct |
12 ms |
8868 KB |
Output is correct |
23 |
Correct |
13 ms |
8868 KB |
Output is correct |
24 |
Correct |
17 ms |
8868 KB |
Output is correct |
25 |
Correct |
16 ms |
8868 KB |
Output is correct |
26 |
Correct |
15 ms |
8868 KB |
Output is correct |
27 |
Correct |
13 ms |
8868 KB |
Output is correct |
28 |
Correct |
12 ms |
8868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7928 KB |
Output is correct |
2 |
Correct |
10 ms |
8168 KB |
Output is correct |
3 |
Correct |
8 ms |
8168 KB |
Output is correct |
4 |
Correct |
8 ms |
8168 KB |
Output is correct |
5 |
Correct |
10 ms |
8168 KB |
Output is correct |
6 |
Correct |
9 ms |
8576 KB |
Output is correct |
7 |
Correct |
15 ms |
8576 KB |
Output is correct |
8 |
Correct |
15 ms |
8592 KB |
Output is correct |
9 |
Correct |
15 ms |
8608 KB |
Output is correct |
10 |
Correct |
21 ms |
8624 KB |
Output is correct |
11 |
Correct |
20 ms |
8624 KB |
Output is correct |
12 |
Correct |
13 ms |
8624 KB |
Output is correct |
13 |
Correct |
19 ms |
8640 KB |
Output is correct |
14 |
Correct |
16 ms |
8768 KB |
Output is correct |
15 |
Correct |
17 ms |
8768 KB |
Output is correct |
16 |
Correct |
15 ms |
8768 KB |
Output is correct |
17 |
Correct |
15 ms |
8768 KB |
Output is correct |
18 |
Correct |
16 ms |
8768 KB |
Output is correct |
19 |
Correct |
14 ms |
8768 KB |
Output is correct |
20 |
Correct |
14 ms |
8768 KB |
Output is correct |
21 |
Correct |
12 ms |
8868 KB |
Output is correct |
22 |
Correct |
12 ms |
8868 KB |
Output is correct |
23 |
Correct |
13 ms |
8868 KB |
Output is correct |
24 |
Correct |
17 ms |
8868 KB |
Output is correct |
25 |
Correct |
16 ms |
8868 KB |
Output is correct |
26 |
Correct |
15 ms |
8868 KB |
Output is correct |
27 |
Correct |
13 ms |
8868 KB |
Output is correct |
28 |
Correct |
12 ms |
8868 KB |
Output is correct |
29 |
Correct |
11 ms |
8868 KB |
Output is correct |
30 |
Correct |
15 ms |
8868 KB |
Output is correct |
31 |
Correct |
197 ms |
35496 KB |
Output is correct |
32 |
Correct |
225 ms |
35656 KB |
Output is correct |
33 |
Correct |
56 ms |
35656 KB |
Output is correct |
34 |
Correct |
4903 ms |
35656 KB |
Output is correct |
35 |
Correct |
3907 ms |
35656 KB |
Output is correct |
36 |
Correct |
40 ms |
35656 KB |
Output is correct |
37 |
Correct |
6499 ms |
35656 KB |
Output is correct |
38 |
Correct |
6297 ms |
35656 KB |
Output is correct |
39 |
Correct |
7097 ms |
35656 KB |
Output is correct |
40 |
Execution timed out |
8042 ms |
35656 KB |
Time limit exceeded |
41 |
Halted |
0 ms |
0 KB |
- |