oj.uz

Submission #59018

# Submission time Handle Problem Language Result Execution time Memory
59018 2018-07-20T06:55:53 Z choikiwon Sandwich (JOI16_sandwich) C++17
0 / 100
 3 ms 488 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 456;

int N, M;
char G[MN][MN];
priority_queue<pii> pq;
int dist[MN * MN * 2], cnt1[MN * MN * 2], cnt2[MN * MN * 2];

int f(int r, int c, int t) {
    return r * (2 * M) + c * 2 + t;
}

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++) dist[ f(i, j, k) ] = 1e9;
    for(int i = 0; i < M; i++) {
        cnt1[ f(0, i, 1) ] = 1;
        cnt1[ f(N - 1, i, 0) ] = 1;
    }
    for(int i = 0; i < N; i++) {
        cnt2[ f(i, 0, G[i][0] == 'Z') ] = 1;
        cnt2[ f(i, M - 1, G[i][M - 1] == 'N') ] = 1;
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 2; k++) {
                if(cnt1[ f(i, j, k) ] && cnt2[ f(i, j, k) ]) {
                    dist[ f(i, j, k) ] = 1;
                    pq.push({ -1, f(i, j, k) });

                    //cout << i << ' ' << j << ' ' << k << endl;
                }
            }
        }
    }
    while(!pq.empty()) {
        int u = pq.top().second;;
        int ud = -pq.top().first;
        pq.pop();

        int r = u / (2 * M);
        int c = (u % (2 * M)) / 2;
        int t = u % 2;

        //cout << r << ' ' << c << ' ' << t << ' ' << dist[u] << endl;

        if(dist[u] < ud) continue;
        if(dist[ f(r, c, t ^ 1) ] > dist[u] + 1) {
            dist[ f(r, c, t ^ 1) ] = dist[u] + 1;
            pq.push({ -dist[ f(r, c, t ^ 1) ], f(r, c, t ^ 1) });
        }
        if(t) {
            int nr = r - 1;
            int nc = c;
            if(0 <= nr) {
                cnt1[ f(nr, nc, 0) ] = 1;
                if(cnt1[ f(nr, nc, 0) ] && cnt2[ f(nr, nc, 0) ] && dist[ f(nr, nc, 0) ] > dist[u] + 1) {
                    dist[ f(nr, nc, 0) ] = dist[u] + 1;
                    pq.push({ -dist[ f(nr, nc, 0) ], f(nr, nc, 0) });
                }
            }
        }
        else {
            int nr = r + 1;
            int nc = c;
            if(nr < N) {
                cnt1[ f(nr, nc, 1) ] = 1;
                if(cnt1[ f(nr, nc, 1) ] && cnt2[ f(nr, nc, 1) ] && dist[ f(nr, nc, 1) ] > dist[u] + 1) {
                    dist[ f(nr, nc, 1) ] = dist[u] + 1;
                    pq.push({ -dist[ f(nr, nc, 1) ], f(nr, nc, 1) });
                }
            }
        }
        if(t ^ (G[r][c] == 'N')) {
            int nr = r;
            int nc = c - 1;
            if(0 <= nc) {
                cnt2[ f(nr, nc, G[nr][nc] == 'N') ] = 1;
                if(cnt1[ f(nr, nc, G[nr][nc] == 'N') ] && cnt2[ f(nr, nc, G[nr][nc] == 'N') ] && dist[ f(nr, nc, G[nr][nc] == 'N') ] > dist[u] + 1) {
                    dist[ f(nr, nc, G[nr][nc] == 'N') ] = dist[u] + 1;
                    pq.push({ -dist[ f(nr, nc, G[nr][nc] == 'N') ], f(nr, nc, G[nr][nc] == 'N') });
                }
            }
        }
        else {
            int nr = r;
            int nc = c + 1;
            if(nc < M) {
                cnt2[ f(nr, nc, G[nr][nc] == 'Z') ] = 1;
                if(cnt1[ f(nr, nc, G[nr][nc] == 'Z') ] && cnt2[ f(nr, nc, G[nr][nc] == 'Z') ] && dist[ f(nr, nc, G[nr][nc] == 'Z') ] > dist[u] + 1) {
                    dist[ f(nr, nc, G[nr][nc] == 'Z') ] = dist[u] + 1;
                    pq.push({ -dist[ f(nr, nc, G[nr][nc] == 'Z') ], f(nr, nc, G[nr][nc] == 'Z') });
                }
            }
        }
    }

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(dist[ f(i, j, 0) ] != 1e9 && dist[ f(i, j, 1) ] != 1e9) printf("%d ", min(dist[ f(i, j, 0) ], dist[ f(i, j, 1) ]) + 1);
            else printf("-1 ");
        }
        printf("\n");
    }
}

Compilation message

sandwich.cpp: In function 'int main()':
sandwich.cpp:18: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:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:23:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%c", &G[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Incorrect 3 ms 488 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Incorrect 3 ms 488 KB Output isn't correct
6 Halted 0 ms 0 KB -