Submission #1153909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153909		brover29	Furniture (JOI20_furniture)	C++20	0 / 100	2 ms	2628 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],mn[N][N],mx[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];
    mx[v.f][v.s]=max(mx[v.f][v.s],mx[u.f][u.s]);
    mn[v.f][v.s]=min(mn[v.f][v.s],mn[u.f][u.s]);
}
bool try_uni(ll x,ll y){
    ll maxx=x;
    ll minn=x;
    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';
            maxx=max(maxx,mx[nw.f][nw.s]);
            minn=min(minn,mn[nw.f][nw.s]);
        }
    }
    if(maxx==n&&minn==1){
        return 0;
    }
    mx[x][y]=x;
    mn[x][y]=x;
    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;
            mx[i][j]=i;
            mn[i][j]=i;
            if(!a[i][j])mn[i][j]=1e18,mx[i][j]=-1e18;


        }
    }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