Submission #516513

#	Time	Username	Problem	Language	Result	Execution time	Memory
516513		leinad2	Furniture (JOI20_furniture)	C++17	100 / 100	438 ms	19184 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
int n, m, i, j, k, a, b, q, A[1010][1010], vis[1010][1010], chk[1010][1010], B[2010];
bool dfs(int a, int b)
{
    if(chk[a][b])return vis[a][b];
    chk[a][b]=1;
    if(a==n&&b==m)return vis[a][b]=1;
    if(a<n&&A[a+1][b]==0&&dfs(a+1, b))vis[a][b]=1;
    if(b<m&&A[a][b+1]==0&&dfs(a, b+1))vis[a][b]=1;
    return vis[a][b];

}
void dfs2(int a, int b)
{
    vis[a][b]=0;
    B[a+b]--;
    if(a<n&&vis[a+1][b-1]==0&&vis[a+1][b]==1)dfs2(a+1, b);
    if(b<m&&vis[a-1][b+1]==0&&vis[a][b+1]==1)dfs2(a, b+1);
}
void dfs3(int a, int b)
{
    vis[a][b]=0;
    B[a+b]--;
    if(a>0&&vis[a-1][b+1]==0&&vis[a-1][b]==1)dfs3(a-1, b);
    if(b>0&&vis[a+1][b-1]==0&&vis[a][b-1]==1)dfs3(a, b-1);
}
void print()
{
    puts("START");
    for(int i=0;i++<n;)
    {
        for(int j=0;j++<m;)printf("%d ", vis[i][j]);
        puts("");
    }
    puts("END");
}
main()
{
    for(scanf("%d %d", &n, &m);i++<n;)for(j=0;j++<m;)scanf("%d", &A[i][j]);
    dfs(1, 1);
    for(i=0;i++<n;)for(j=0;j++<m;)B[i+j]+=vis[i][j];
    for(scanf("%d", &q);q--;)
    {
        scanf("%d %d", &a, &b);
        if(vis[a][b]==0)
        {
            puts("1");
            A[a][b]=1;
        }
        else
        {
            if(B[a+b]!=1)
            {
                puts("1");
                A[a][b]=1;
                dfs2(a, b);
                dfs3(a, b);
                B[a+b]++;
            }
            else puts("0");
        }
    }
}

Compilation message (stderr)

furniture.cpp: In function 'bool dfs(int, int)':
furniture.cpp:8:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    8 |     if(a==n&&b==m)return vis[a][b]=1;
      |                          ~~~~~~~~~^~
furniture.cpp: At global scope:
furniture.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main()
      | ^~~~
furniture.cpp: In function 'int main()':
furniture.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(scanf("%d %d", &n, &m);i++<n;)for(j=0;j++<m;)scanf("%d", &A[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:40:59: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     for(scanf("%d %d", &n, &m);i++<n;)for(j=0;j++<m;)scanf("%d", &A[i][j]);
      |                                                      ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     for(scanf("%d", &q);q--;)
      |         ~~~~~^~~~~~~~~~
furniture.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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