#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 444;
ll cross(pii a, pii b) {
return 1LL * a.first * b.second - 1LL * a.second * b.first;
}
ll ccw(pii a, pii b, pii c) {
pii p = pii(b.first - a.first, b.second - a.second);
pii q = pii(c.first - a.first, c.second - a.second);
return cross(p, q);
}
int N, M;
char G[MN][MN];
vector<int> adj[MN * MN * 2], radj[MN * MN * 2];
int deg[MN * MN * 2], sz[MN * MN * 2];
int f(int r, int c, int up) {
return 2 * (r * M + c) + up;
}
pii g(int x) {
return pii((x / 2) / M, (x / 2) % M);
}
int vis[MN * MN * 2];
int X;
void go(int u, int dir) {
if(vis[u] == 1) {
X = u;
return;
}
vis[u] = 1;
if(radj[u].size() == 0) return;
if(radj[u].size() == 1) {
go(radj[u][0], dir);
return;
}
int x = radj[u][0];
int y = radj[u][1];
if((ccw(g(u), g(x), g(y)) > 0) == dir) go(y, dir);
else go(x, dir);
}
int find(int u) {
if(radj[u].size() < 2) return -1;
int x = radj[u][0];
int y = radj[u][1];
if(deg[x] || deg[y]) return -1;
memset(vis, 0, sizeof(vis));
X = -1;
go(x, ccw(g(u), g(x), g(y)) > 0);
go(y, ccw(g(u), g(y), g(x)) > 0);
return X;
}
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++) {
if(G[i][j] == 'N') {
if(i) adj[ f(i - 1, j, 1) ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
if(j < M - 1) adj[ f(i, j + 1, G[i][j + 1] == 'N') ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
if(i < N - 1) adj[ f(i + 1, j, 0) ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
if(j) adj[ f(i, j - 1, G[i][j - 1] == 'Z') ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
}
if(G[i][j] == 'Z') {
if(i) adj[ f(i - 1, j, 1) ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
if(j) adj[ f(i, j - 1, G[i][j - 1] == 'Z') ].push_back(f(i, j, 1)), deg[ f(i, j, 1) ]++;
if(i < N - 1) adj[ f(i + 1, j, 0) ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
if(j < M - 1) adj[ f(i, j + 1, G[i][j + 1] == 'N') ].push_back(f(i, j, 0)), deg[ f(i, j, 0) ]++;
}
}
}
for(int u = 0; u < N * M * 2; u++) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
radj[v].push_back(u);
}
}
queue<int> q;
for(int i = 0; i < N * M * 2; i++) if(!deg[i]) {
q.push(i);
}
while(!q.empty()) {
int u = q.front(); q.pop();
sz[u]++;
int x = find(u);
if(x != -1) sz[u] -= sz[x];
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
sz[v] += sz[u];
deg[v]--;
if(!deg[v]) {
q.push(v);
}
}
}
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
int t1 = deg[ f(i, j, 1) ] == 0? sz[ f(i, j, 1) ] : 1e9;
int t2 = deg[ f(i, j, 0) ] == 0? sz[ f(i, j, 0) ] : 1e9;
if(min(t1, t2) == 1e9) printf("-1 ");
else printf("%d ", 2 * min(t1, t2));
}
printf("\n");
}
}
Compilation message
sandwich.cpp: In function 'int main()':
sandwich.cpp:94:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
sandwich.cpp:111:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
sandwich.cpp:68: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:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("\n");
~~~~~^~~~~~
sandwich.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%c", &G[i][j]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 2 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 3 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 4 |
Correct |
19 ms |
18888 KB |
Output is correct |
| 5 |
Correct |
21 ms |
20472 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19340 KB |
Output is correct |
| 7 |
Correct |
377 ms |
20856 KB |
Output is correct |
| 8 |
Correct |
421 ms |
20812 KB |
Output is correct |
| 9 |
Correct |
318 ms |
20728 KB |
Output is correct |
| 10 |
Correct |
421 ms |
20856 KB |
Output is correct |
| 11 |
Incorrect |
497 ms |
20856 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 2 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 3 |
Correct |
19 ms |
18808 KB |
Output is correct |
| 4 |
Correct |
19 ms |
18888 KB |
Output is correct |
| 5 |
Correct |
21 ms |
20472 KB |
Output is correct |
| 6 |
Correct |
21 ms |
19340 KB |
Output is correct |
| 7 |
Correct |
377 ms |
20856 KB |
Output is correct |
| 8 |
Correct |
421 ms |
20812 KB |
Output is correct |
| 9 |
Correct |
318 ms |
20728 KB |
Output is correct |
| 10 |
Correct |
421 ms |
20856 KB |
Output is correct |
| 11 |
Incorrect |
497 ms |
20856 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
