Submission #1198814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198814		Marco_Escandon	Furniture (JOI20_furniture)	C++20	0 / 100	4 ms	1032 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
vector<vector<ll>> cad,cad2;
vector<set<pair<ll,ll>>> s;
ll dfs(ll x, ll y)
{
    if(x==n-1&&y==m-1) return 0;
    if(x==n||y==m||cad[x][y]==1) return 1;
    if(cad2[x][y]!=-1) return cad2[x][y];
    return cad2[x][y]=min(dfs(x+1,y),dfs(x,y+1));
}
ll dx[]={1,0,-1,0};
ll dy[]={0,-1,0,1};
void dfs2(ll x, ll y)
{
    if(x<0||x>=n||y<0||y>=m||cad2[x][y]==1) return;
    ll o1=1;if(x<n-1) o1=cad[x+1][y];
    ll o2=1;if(y<m-1) o2=cad[x][y+1];
    cad2[x][y]=min(o1,o2);
    o1=1;if(x>0) o1=cad[x-1][y];
    o2=1;if(y>0) o2=cad[x][y-1];
    cad2[x][y]=max(cad2[x][y],min(o1,o2));
    if(cad2[x][y]==0) return;
    s[x+y].erase({x,y});
    for(int i=0; i<4; i++)
        dfs2(x+dx[i],y+dy[i]);
}
int main()
{
    cin>>n>>m;
    cad.assign(n,vector<ll>(m, 0));
    cad2.assign(n,vector<ll>(m, -1));
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            cin>>cad[i][j];
    dfs(0,0);
    s.resize(n+m+5);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            if(cad2[i][j]==0) s[i+j].insert({i,j});
            if(cad2[i][j]==-1) cad2[i][j]=1;
        }
            
    ll q;
    cin>>q;
    while(q--)
    {
        ll a,b;
        cin>>a>>b;
        a--; b--;
        if(s[a+b].size()-(s[a+b].find({a,b})!=s[a+b].end())>=1)
        {
            cout<<"1\n";
            if(s[a+b].find({a,b})!=s[a+b].end())
            s[a+b].erase({a,b});
            cad2[a][b]=1;
            for(int i=0; i<4; i++)
            {
                dfs2(a+dx[i],b+dy[i]);
            }
        }
        else cout<<"0\n";
    }
}

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