oj.uz

답안 #126163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126163 2019-07-07T07:00:35 Z choikiwon Sandwich (JOI16_sandwich) C++17
0 / 100
 31 ms 11384 KB 
#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], 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

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
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11128 KB Output is correct
2 Correct 19 ms 11128 KB Output is correct
3 Correct 12 ms 11128 KB Output is correct
4 Correct 12 ms 11128 KB Output is correct
5 Correct 12 ms 11128 KB Output is correct
6 Correct 31 ms 11384 KB Output is correct
7 Incorrect 24 ms 11384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 11128 KB Output is correct
2 Correct 19 ms 11128 KB Output is correct
3 Correct 12 ms 11128 KB Output is correct
4 Correct 12 ms 11128 KB Output is correct
5 Correct 12 ms 11128 KB Output is correct
6 Correct 31 ms 11384 KB Output is correct
7 Incorrect 24 ms 11384 KB Output isn't correct
8 Halted 0 ms 0 KB -