Submission #126164

#	Time	Username	Problem	Language	Result	Execution time	Memory
126164		choikiwon	Sandwich (JOI16_sandwich)	C++17	35 / 100	8058 ms	30292 KiB

sandwich

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 444;

int N, M;
char G[MN][MN];
vector<int> adj[MN * MN * 2];

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

int tin[MN * MN * 2], tout[MN * MN * 2], timer, cnt;
int ans[MN * MN * 2];

void dfs(int u) {
    tin[u] = timer++;
    cnt++;

    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];

        if(tin[v] != -1) {
            if(tin[v] < tin[u] && tout[v] == -1) cnt = 1e9;
            continue;
        }
        dfs(v);
    }

    tout[u] = timer;
}

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, j, 1) ].push_back(f(i - 1, j, 1));
                if(j < M - 1) adj[ f(i, j, 1) ].push_back(f(i, j + 1, G[i][j + 1] == 'N'));
                if(i < N - 1) adj[ f(i, j, 0) ].push_back(f(i + 1, j, 0));
                if(j) adj[ f(i, j, 0) ].push_back(f(i, j - 1, G[i][j - 1] == 'Z'));
            }
            if(G[i][j] == 'Z') {
                if(i) adj[ f(i, j, 1) ].push_back(f(i - 1, j, 1));
                if(j) adj[ f(i, j, 1) ].push_back(f(i, j - 1, G[i][j - 1] == 'Z'));
                if(i < N - 1) adj[ f(i, j, 0) ].push_back(f(i + 1, j, 0));
                if(j < M - 1) adj[ f(i, j, 0) ].push_back(f(i, j + 1, G[i][j + 1] == 'N'));
            }
        }
    }

    for(int i = 0; i < M; i++) {
        memset(tin, -1, sizeof(tin));
        memset(tout, -1, sizeof(tout));
        timer = 0;
        cnt = 0;

        for(int j = 0; j < N; j++) {
            if(tin[ f(j, i, 1) ] == -1) dfs(f(j, i, 1));
            ans[ f(j, i, 1) ] = cnt;
        }
        memset(tin, -1, sizeof(tin));
        memset(tout, -1, sizeof(tout));
        timer = 0;
        cnt = 0;

        for(int j = N - 1; j >= 0; j--) {
            if(tin[ f(j, i, 0) ] == -1) dfs(f(j, i, 0));
            ans[ f(j, i, 0) ] = cnt;
        }
    }

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

Compilation message (stderr)

sandwich.cpp: In function 'void dfs(int)':
sandwich.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
sandwich.cpp: In function 'int main()':
sandwich.cpp:38: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:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
sandwich.cpp:43: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: 35 / 35
• Subtask 2: 0 / 65