Submission #319975

#	Time	Username	Problem	Language	Result	Execution time	Memory
319975		jamezzz	Furniture (JOI20_furniture)	C++14	0 / 100	5086 ms	748 KiB

furniture

#include <bits/stdc++.h>
using namespace std;

int n, m, q, x, y, c[1005][1005], cnt[2005];
//cnt[i] stores number of nice paths through (x, y), such that x + y = i
//every nice path must pass through a point such that x + y = i for all i
bool p[1005][1005], vis[1005][1005]; //true if nice path passes through x, y

#define debug

bool dfs(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m) return false;
    if (x == n && y == m){
        p[x][y] = true;
        return true;
    }
    if (c[x][y]) return false;
    if (vis[x][y]) return p[x][y];
    vis[x][y] = true;
    bool b1 = dfs(x + 1, y);
    bool b2 = dfs(x, y + 1);
    p[x][y] = b1 || b2;
    if (p[x][y]) ++cnt[x + y];
    return p[x][y];
}

bool pos(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m) return false;
    return p[x][y];
}

void u1(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (x == 1 && y == 1) return;
    if (x == n && y == m) return;
    if (!p[x][y]) return; //already no path to (x, y)
    if (!(pos(x - 1, y) || pos(x, y - 1))){ //no path to (x, y)
        p[x][y] = false;
        --cnt[x + y];
    }
    else if (!(pos(x - 1, y) || pos(x, y - 1))){
        p[x][y] = false;
        --cnt[x + y];
    }
    u1(x + 1, y);
    u1(x, y + 1);
}

void u2(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m) return;
    if (x == 1 && y == 1) return;
    if (x == n && y == m) return;
    if (!p[x][y]) return; //already no path from (x, y) to (n, m)
    if (!(pos(x + 1, y) || pos(x, y + 1))){ //no path from (x, y) to (n, m)
        p[x][y] = false;
        --cnt[x + y];
    }
    else if (!(pos(x - 1, y) || pos(x, y - 1))){
        p[x][y] = false;
        --cnt[x + y];
    }
    u2(x - 1, y);
    u2(x, y - 1);
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            scanf("%d", &c[i][j]);
        }
    }
    dfs(1, 1);
    scanf("%d", &q);
    for (int i = 0; i < q; ++i){
        #ifdef debug
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
                printf("%d ", p[i][j]);
            }
            printf("\n");
        }
        #endif // debug
        scanf("%d%d", &x, &y);
        if (!p[x][y]){
            //no nice path passes through p[x][y], so just put
            printf("1\n");
            continue;
        }
        if (cnt[x + y] == 1){
            //all nice paths must pass through (x, y), so cannot put
            printf("0\n");
            continue;
        }
        //more than 1 point which nice paths pass through with sum x + y, can put
        printf("1\n");
        p[x][y] = false;
        --cnt[x + y];
        u1(x + 1, y); //update towards (n, m)
        u1(x, y + 1);
        u2(x - 1, y); //update towards (1, 1)
        u2(x, y - 1);
    }
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   70 |             scanf("%d", &c[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95