Submission #401622

#	Time	Username	Problem	Language	Result	Execution time	Memory
401622		qwerasdfzxcl	Sandwich (JOI16_sandwich)	C++14	0 / 100	1 ms	716 KiB

sandwich

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct vertex{
    int x, y;
    bool z; ///up=1
    vertex(){}
    vertex(int _x, int _y, bool _z): x(_x), y(_y), z(_z) {}
};
struct node{
    bool x[50][50];
    int val;
}dp[50][50][2];
int deg[50][50][2], dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}, n, m;
int sb[50][50];
bool visited[50][50][2];
vector<string> matrix;

bool chk(int x, int y){
    return (x>=0 && x<n && y>=0 && y<m);
}

void calc(vertex &V){
    vertex x1, x2;
    if (V.z) x1 = vertex(V.x+1, V.y, V.z);
    else x1 = vertex(V.x-1, V.y, V.z);
    if ((V.z && matrix[V.x][V.y]=='Z') || (!V.z && matrix[V.x][V.y]=='N')) x2 = vertex(V.x, V.y+1, V.z);
    else x2 = vertex(V.x, V.y-1, V.z);
    if (!chk(x1.x, x1.y)) swap(x1, x2);
    x1.z = sb[x1.x][x1.y];
    dp[V.x][V.y][V.z].val = dp[x1.x][x1.y][x1.z].val+1;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) dp[V.x][V.y][V.z].x[i][j] = dp[x1.x][x1.y][x1.z].x[i][j];
    }
    //if (V.x==1 && V.y==1 && V.z==1) printf("  %d %d %d\n  %d %d %d\n", x1.x, x1.y, x1.z, x2.x, x2.)
    if (!chk(x2.x, x2.y)) return;
    x2.z = sb[x2.x][x2.y];
    int cnt=0;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (dp[V.x][V.y][V.z].x[i][j]&dp[x2.x][x2.y][x2.z].x[i][j]) cnt++;
            dp[V.x][V.y][V.z].x[i][j] |= dp[x2.x][x2.y][x2.z].x[i][j];
        }
    }
    dp[V.x][V.y][V.z].x[V.x][V.y] = 1;
    dp[V.x][V.y][V.z].val += dp[x2.x][x2.y][x2.z].val-cnt;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for (int i=0;i<n;i++){
        string tmp;
        cin >> tmp;
        matrix.push_back(tmp);
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) sb[i][j] = -1;
    }
    queue<vertex> q;
    if (matrix[0][0]=='Z'){
        q.push(vertex(0, 0, 0));
        dp[0][0][0].val = 1;
        dp[0][0][0].x[0][0] = 1;
        sb[0][0] = 0;
    }
    if (matrix[0][m-1]=='N'){
        q.push(vertex(0, m-1, 0));
        dp[0][m-1][0].val = 1;
        dp[0][m-1][0].x[0][m-1] = 1;
        sb[0][m-1] = 0;
    }
    if (matrix[n-1][0]=='N'){
        q.push(vertex(n-1, 0, 1));
        dp[n-1][0][1].val = 1;
        dp[n-1][0][1].x[n-1][0] = 1;
        sb[n-1][0] = 1;
    }
    if (matrix[n-1][m-1]=='Z'){
        q.push(vertex(n-1, m-1, 1));
        dp[n-1][m-1][1].val = 1;
        dp[n-1][m-1][1].x[n-1][m-1] = 1;
        sb[n-1][m-1] = 1;
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) deg[i][j][0] = deg[i][j][1] = 2;
    }
    for (int j=0;j<m;j++) deg[0][j][0]--, deg[n-1][j][1]--;
    for (int i=0;i<n;i++){
        if (matrix[i][0]=='Z') deg[i][0][0]--;
        else deg[i][0][1]--;
        if (matrix[i][m-1]=='N') deg[i][m-1][0]--;
        else deg[i][m-1][1]--;
    }
    /*for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) printf("%d ", deg[i][j][0]);
        printf("\n");
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) printf("%d ", deg[i][j][1]);
        printf("\n");
    }*/
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        if (visited[cur.x][cur.y][cur.z]) continue;
        visited[cur.x][cur.y][cur.z] = 1;
        for (int k=0;k<4;k++){
            vertex nxt = vertex(cur.x+dx[k], cur.y+dy[k], 0);
            if (!chk(nxt.x, nxt.y)) continue;
            if (k==1) nxt.z = 1;
            else if (k==2 && matrix[nxt.x][nxt.y]=='N') nxt.z = 1;
            else if (k==3 && matrix[nxt.x][nxt.y]=='Z') nxt.z = 1;
            if (cur.z==sb[cur.x][cur.y])deg[nxt.x][nxt.y][nxt.z]--;
            if (!deg[nxt.x][nxt.y][nxt.z]){
                //printf(" %d %d %d: %d %d %d, %d\n", nxt.x, nxt.y, nxt.z, cur.x, cur.y, cur.z, sb[cur.x][cur.y]);
                q.push(nxt);
                calc(nxt);
                if (sb[nxt.x][nxt.y]==-1) sb[nxt.x][nxt.y] = nxt.z;
            }
        }
    }
/*
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) printf("%d ", dp[i][j][0].val);
        printf("\n");
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++) printf("%d ", dp[i][j][1].val);
        printf("\n");
    }
*/
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            int tmp1 = dp[i][j][0].val, tmp2 = dp[i][j][1].val;
            if (!tmp1 && !tmp2) printf("-1 ");
            else if (!tmp1) printf("%d ", tmp2*2);
            else if (!tmp2) printf("%d ", tmp1*2);
            else printf("%d ", min(tmp1, tmp2)*2);
        }
        printf("\n");
    }
    return 0;
}

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