Submission #436919

#	Time	Username	Problem	Language	Result	Execution time	Memory
436919		qwerasdfzxcl	Sandwich (JOI16_sandwich)	C++14	35 / 100	290 ms	262144 KiB

sandwich

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
char matrix[404][404];
int visited[404][404][2];
int dp[404][404][2], dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1}, n, m, deg[404][404][2];
vector<pair<short, short>> col[404][404][2];

bool valid(int x, int y){
    return ((1<=x && x<=n) && (1<=y && y<=m));
}
/*
int count_visited(){
    int ret = 0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (visited[i][j][0] || visited[i][j][1]) ret++;
    }
    return ret;
}*/

vector<pair<short, short>> combine(vector<pair<short, short>> &X, vector<pair<short, short>> &Y){
    vector<pair<short, short>> ret(n+1);
    for (int i=1;i<=n;i++){
        if (X[i].first==m || Y[i].first==m) ret[i].first = ret[i].second = m;
        else{
            ret[i].first = max(X[i].first, Y[i].first);
            ret[i].second = max(X[i].second, Y[i].second);
            if (ret[i].first+ret[i].second>=m) ret[i].first = ret[i].second = m;
        }
    }
    return ret;
}

int calc(int x, int y, int c){
    int ret = 0;
    for (int i=1;i<=n;i++){
        if (col[x][y][c][i].first==m) ret += m;
        else ret += col[x][y][c][i].first+col[x][y][c][i].second;
    }
    return ret;
}

bool dfs(int x, int y, int c){
    if (visited[x][y][c]) return (visited[x][y][c]==1e9 && dp[x][y][c]!=1e9);
    visited[x][y][c] = c+1;

    bool ret = 1;
    vector<pair<short, short>> tmp1(n+1), tmp2(n+1);
    int nx1 = x+dx[c], nx2 = y+dy[c];
    if (valid(nx1, nx2)){
        ret &= dfs(nx1, nx2, c);
        tmp1 = col[nx1][nx2][c];
        deg[nx1][nx2][c]++;
        if (deg[nx1][nx2][c]==2){
            col[nx1][nx2][c].clear();
            col[nx1][nx2][c].shrink_to_fit();
        }
    }
    int d = 2;
    if (!c && matrix[x][y]=='Z') d = 3;
    if (c && matrix[x][y]=='N') d = 3;
    int nx3 = x+dx[d], nx4 = y+dy[d];
    if (valid(nx3, nx4)){
        if (d==2 && matrix[nx3][nx4]=='N'){
            ret &= dfs(nx3, nx4, 0);
            tmp2 = col[nx3][nx4][0];
            deg[nx3][nx4][0]++;
            if (deg[nx3][nx4][0]==2){
                col[nx3][nx4][0].clear();
                col[nx3][nx4][0].shrink_to_fit();
            }
        }
        else if (d==3 && matrix[nx3][nx4]=='Z'){
             ret &= dfs(nx3, nx4, 0);
             tmp2 = col[nx3][nx4][0];
             deg[nx3][nx4][0]++;
            if (deg[nx3][nx4][0]==2){
                col[nx3][nx4][0].clear();
                col[nx3][nx4][0].shrink_to_fit();
            }
        }
        else{
            ret &= dfs(nx3, nx4, 1);
            tmp2 = col[nx3][nx4][1];
            deg[nx3][nx4][1]++;
            if (deg[nx3][nx4][1]==2){
                col[nx3][nx4][1].clear();
                col[nx3][nx4][1].shrink_to_fit();
            }
        }
    }
    visited[x][y][c] = 1e9;
    if (ret){
        col[x][y][c] = combine(tmp1, tmp2);
        if (d==2) col[x][y][c][x].second = m+1-y;
        else col[x][y][c][x].first = y;
        if (col[x][y][c][x].first+col[x][y][c][x].second==m) col[x][y][c][x].first = col[x][y][c][x].second = m;
        dp[x][y][c] = calc(x, y, c);
    }
    return ret;
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        scanf("%s", matrix[i]+1);
        for (int j=1;j<=m;j++) dp[i][j][0] = dp[i][j][1] = 1e9;
    }
    vector<pair<short, short>> v;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) v.emplace_back(i, j);
    }
    random_shuffle(v.begin(), v.end());
    for (auto &p:v){
        for (int k=0;k<2;k++) if (!visited[p.first][p.second][k]) dfs(p.first, p.second, k);
    }
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=0;k<2;k++) if (!visited[i][j][k]) dfs(i, j, k);
        }
    }*/
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            int ans = min(dp[i][j][0], dp[i][j][1]);
            if (ans==1e9) ans = -1;
            else ans <<= 1;
            printf("%d ", ans);
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

sandwich.cpp: In function 'int main()':
sandwich.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sandwich.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%s", matrix[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 35 / 35
• Subtask 2: 0 / 65