Submission #59012

#	Time	Username	Problem	Language	Result	Execution time	Memory
59012		choikiwon	Sandwich (JOI16_sandwich)	C++17	0 / 100	3 ms	640 KiB

sandwich

#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], cnt[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++) {
        cnt[ f(0, i, 1) ]++;
        cnt[ f(N - 1, i, 0) ]++;
    }
    for(int i = 0; i < N; i++) {
        cnt[ f(i, 0, G[i][0] == 'Z') ]++;
        cnt[ f(i, M - 1, G[i][M - 1] == 'N') ]++;
    }
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            for(int k = 0; k < 2; k++) {
                if(cnt[ f(i, j, k) ] == 2) {
                    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[ 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 && dist[ f(nr, nc, 0) ] > dist[u] + 1) {
                cnt[ f(nr, nc, 0) ]++;
                if(cnt[ f(nr, nc, 0) ] == 2) {
                    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 && dist[ f(nr, nc, 1) ] > dist[u] + 1) {
                cnt[ f(nr, nc, 1) ]++;
                if(cnt[ f(nr, nc, 1) ] == 2) {
                    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 && dist[ f(nr, nc, G[nr][nc] == 'N') ] > dist[u] + 1) {
                cnt[ f(nr, nc, G[nr][nc] == 'N') ]++;
                if(cnt[ f(nr, nc, G[nr][nc] == 'N') ] == 2) {
                    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 && dist[ f(nr, nc, G[nr][nc] == 'Z') ] > dist[u] + 1) {
                cnt[ f(nr, nc, G[nr][nc] == 'Z') ]++;
                if(cnt[ f(nr, nc, G[nr][nc] == 'Z') ] == 2) {
                    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 (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:50:13: warning: unused variable 'ud' [-Wunused-variable]
         int ud = -pq.top().first;
             ^~
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
• Subtask 2: 0 / 65