oj.uz

Submission #258010

# Submission time Handle Problem Language Result Execution time Memory
258010 2020-08-05T08:12:03 Z 반딧불(#5055) Sandwich (JOI16_sandwich) C++17
35 / 100
 8000 ms 3100 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int arr[405][405];
int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0}; /// R, D, L, U

int visited[405][405];
int ans[405][405];

const int LINK[2][2][2] = { /// 'N' = 0, 'Z' = 1 | up : 0, down : 1 (input)
    1, 2,
    0, 3,
    0, 1,
    2, 3
};
const int DIR[2][4] = { /// ���, ����
    0, 1, 1, 0,
    1, 1, 0, 0
};

int dfs(int x, int y, int t){
    if(visited[x][y]){
        return visited[x][y] == 1 ? 1e9 : 0;
    }
    visited[x][y] = 1;
    int ret = 2;
    for(int i=0; i<2; i++){
        int d = LINK[arr[x][y]][t][i];
        int tx = x+xx[d], ty = y+yy[d];
        if(tx < 1 || tx > n || ty < 1 || ty > m) continue;
        ret += dfs(tx, ty, DIR[arr[tx][ty]][2^d]);
        if(ret >= 1e9) return 1e9;
    }
    visited[x][y] = 2;
    return ret;
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf(" %c", &arr[i][j]);
            if(arr[i][j] == 'N') arr[i][j] = 0;
            else arr[i][j] = 1;
            ans[i][j] = 1e9;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int t=0; t<=1; t++){
                memset(visited, 0, sizeof(visited));
                ans[i][j] = min(ans[i][j], dfs(i, j, t));
            }
            printf("%d ", ans[i][j] == 1e9 ? -1 : ans[i][j]);
        }
        puts("");
    }
}

Compilation message

sandwich.cpp: In function 'int main()':
sandwich.cpp:46:36: warning: format '%c' expects argument of type 'char*', but argument 2 has type 'int*' [-Wformat=]
             scanf(" %c", &arr[i][j]);
                          ~~~~~~~~~~^
sandwich.cpp:43: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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 112 ms 1272 KB Output is correct
7 Correct 169 ms 1152 KB Output is correct
8 Correct 183 ms 1152 KB Output is correct
9 Correct 129 ms 1152 KB Output is correct
10 Correct 237 ms 1272 KB Output is correct
11 Correct 268 ms 1272 KB Output is correct
12 Correct 103 ms 1024 KB Output is correct
13 Correct 255 ms 1272 KB Output is correct
14 Correct 250 ms 1152 KB Output is correct
15 Correct 167 ms 1272 KB Output is correct
16 Correct 151 ms 1304 KB Output is correct
17 Correct 168 ms 1152 KB Output is correct
18 Correct 155 ms 1400 KB Output is correct
19 Correct 157 ms 1152 KB Output is correct
20 Correct 154 ms 1152 KB Output is correct
21 Correct 150 ms 1400 KB Output is correct
22 Correct 157 ms 1152 KB Output is correct
23 Correct 164 ms 1152 KB Output is correct
24 Correct 248 ms 1272 KB Output is correct
25 Correct 252 ms 1152 KB Output is correct
26 Correct 239 ms 1152 KB Output is correct
27 Correct 257 ms 1400 KB Output is correct
28 Correct 189 ms 1272 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 112 ms 1272 KB Output is correct
7 Correct 169 ms 1152 KB Output is correct
8 Correct 183 ms 1152 KB Output is correct
9 Correct 129 ms 1152 KB Output is correct
10 Correct 237 ms 1272 KB Output is correct
11 Correct 268 ms 1272 KB Output is correct
12 Correct 103 ms 1024 KB Output is correct
13 Correct 255 ms 1272 KB Output is correct
14 Correct 250 ms 1152 KB Output is correct
15 Correct 167 ms 1272 KB Output is correct
16 Correct 151 ms 1304 KB Output is correct
17 Correct 168 ms 1152 KB Output is correct
18 Correct 155 ms 1400 KB Output is correct
19 Correct 157 ms 1152 KB Output is correct
20 Correct 154 ms 1152 KB Output is correct
21 Correct 150 ms 1400 KB Output is correct
22 Correct 157 ms 1152 KB Output is correct
23 Correct 164 ms 1152 KB Output is correct
24 Correct 248 ms 1272 KB Output is correct
25 Correct 252 ms 1152 KB Output is correct
26 Correct 239 ms 1152 KB Output is correct
27 Correct 257 ms 1400 KB Output is correct
28 Correct 189 ms 1272 KB Output is correct
29 Correct 20 ms 1024 KB Output is correct
30 Correct 20 ms 2304 KB Output is correct
31 Execution timed out 8077 ms 3100 KB Time limit exceeded
32 Halted 0 ms 0 KB -