oj.uz

Submission #55397

# Submission time Handle Problem Language Result Execution time Memory
55397 2018-07-07T07:32:29 Z 강태규(#1543) Sandwich (JOI16_sandwich) C++11
0 / 100
 11 ms 8376 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int r, c;
char grid[401][401];
vector<int> edge[2][401][401];
int used[2][400][400];
int fin[2][400][400];
 
void intToNode(int &t, int &x, int &y, int i) {
    y = i & 1023;
    x = (i >> 10) & 1023;
    t = i >> 20;
}

const int inf = 1e6;
int dfs(int d) {
    int t, x, y;
    intToNode(t, x, y, d);
    if (fin[t][x][y]) return 0;
    if (used[t][x][y]) return inf;
    used[t][x][y] = 1;
    int ret = 1;
    
    for (int i : edge[t][x][y]) {
        ret += dfs(i);
    }
    fin[t][x][y] = 1;
    return ret;
}

int ans[400][400];

int main() {
    scanf("%d%d", &r, &c);
    for (int i = 0; i < r; ++i) {
        scanf("%s", grid[i]);
    }
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            if (j) edge[0][i][j].push_back((i << 10) | (j - 1));
            if (i + 1 < r) edge[grid[i][j] != 'N'][i][j].push_back(((grid[i + 1][j] != 'N') << 20) | ((i + 1) << 10) | j);
            if (j + 1 < c) edge[1][i][j].push_back((1 << 20) | (i << 10) | (j + 1));
            if (i) edge[grid[i][j] != 'Z'][i][j].push_back(((grid[i][j] != 'Z') << 20) | ((i - 1) << 10) | j);
        }
    }
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < r; ++j) {
            for (int k = 0; k < c; ++k) {
                used[0][j][k] = 0;
                used[1][j][k] = 0;
                fin[0][j][k] = 0;
                fin[1][j][k] = 0;
            }
        }
        int sum = 0;
        for (int j = 0; j < c; ++j) {
            sum += dfs((i << 10) | j);
            ans[i][j] = sum;
        }
    }
    
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < r; ++j) {
            for (int k = 0; k < c; ++k) {
                used[0][j][k] = 0;
                used[1][j][k] = 0;
                fin[0][j][k] = 0;
                fin[1][j][k] = 0;
            }
        }
        int sum = 0;
        for (int j = c; j--; ) {
            sum += dfs((1 << 20) | (i << 10) | j);
            ans[i][j] = min(ans[i][j], sum);
        }
    }
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < c; ++j) {
            printf("%d ", ans[i][j] < inf ? 2 * ans[i][j] : -1);
        }
        printf("\n");
    }
    
	return 0;
}

Compilation message

sandwich.cpp: In function 'int main()':
sandwich.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &r, &c);
     ~~~~~^~~~~~~~~~~~~~~~
sandwich.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", grid[i]);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7928 KB Output is correct
2 Correct 11 ms 8040 KB Output is correct
3 Incorrect 8 ms 8376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7928 KB Output is correct
2 Correct 11 ms 8040 KB Output is correct
3 Incorrect 8 ms 8376 KB Output isn't correct
4 Halted 0 ms 0 KB -