Submission #1153930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153930		brover29	Furniture (JOI20_furniture)	C++20	0 / 100	2 ms	3396 KiB

furniture

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=1005;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,m,a[N][N],mnr[N][N],mxr[N][N],mxc[N][N],mnc[N][N],sz[N][N];
pair<ll,ll>pr[N][N];
ll dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
pair<ll,ll> get(pair<ll,ll> a){
    ll x,y;
    x=a.f;
    y=a.s;
    return (pr[x][y]==make_pair(x,y) ? make_pair(x,y) : pr[x][y]=get(pr[x][y]));
}
void uni(pair<ll,ll>u,pair<ll,ll>v){
    u=get(u);
    v=get(v);
    if(u==v)return;
    if(sz[u.f][u.s]>sz[v.f][v.s])swap(v,u);
    pr[u.f][u.s]=v;
    sz[v.f][v.s]+=sz[u.f][u.s];
    mxc[v.f][v.s]=max(mxc[v.f][v.s],mxc[u.f][u.s]);
    mnc[v.f][v.s]=min(mnc[v.f][v.s],mnc[u.f][u.s]);
    mxr[v.f][v.s]=max(mxr[v.f][v.s],mxr[u.f][u.s]);
    mnr[v.f][v.s]=min(mnr[v.f][v.s],mnr[u.f][u.s]);
}
bool try_uni(ll x,ll y){
    ll maxr=x;
    ll minr=x;
    ll maxc=y;
    ll minc=y;
    for(ll i=0;i<4;i++){
        for(ll j=0;j<4;j++){
            if(dx[i]==0&&dy[j]==0)continue;

            if(!a[x+dx[i]][y+dy[j]])continue;
            pair<ll,ll> nw={x+dx[i],y+dy[j]};
            nw=get(nw);
         //   cout<<mx[2][1]<<'\n';
            maxr=max(maxr,mxr[nw.f][nw.s]);
            minr=min(minr,mnr[nw.f][nw.s]);
            maxc=max(maxc,mxc[nw.f][nw.s]);
            minc=min(minc,mnc[nw.f][nw.s]);
        }
    }
    if((maxr==n&&minr==1)||(maxc==m&&minc==1)){
        return 0;
    }
    mxr[x][y]=x;
    mnr[x][y]=x;
    mxc[x][y]=y;
    mnc[x][y]=y;
    for(ll i=0;i<4;i++){
        for(ll j=0;j<4;j++){
            if(dx[i]==0&&dy[j]==0)continue;
            if(!a[x+dx[i]][y+dy[j]])continue;
            pair<ll,ll> nw={x+dx[i],y+dy[j]};
            nw=get(nw);
            if(nw==get({x,y}))continue;
            uni(nw,get({x,y}));
        }
    }
    a[x][y]=1;
    return 1;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>a[i][j];
            pr[i][j]={i,j};
            sz[i][j]=1;
            ll x=i;
            ll y=j;
            mxr[x][y]=x;
            mnr[x][y]=x;
            mxc[x][y]=y;
            mnc[x][y]=y;


        }
    }for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(!a[i][j])continue;
            ll x=i;
            ll y=j;
            for(ll i=0;i<4;i++){
                for(ll j=0;j<4;j++){
                    if(dx[i]==0&&dy[j]==0)continue;
                    if(!a[x+dx[i]][y+dy[j]])continue;

                    pair<ll,ll> nw={x+dx[i],y+dy[j]};
                    nw=get(nw);
                    if(nw==get({x,y}))continue;
                    uni(nw,get({x,y}));
                }
            }


        }
    }
    ll q;
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        cout<<try_uni(x,y)<<'\n';
    }
}

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