Submission #773075

#	Time	Username	Problem	Language	Result	Execution time	Memory
773075		gagik_2007	Furniture (JOI20_furniture)	C++17	0 / 100	5 ms	1108 KiB

furniture

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=1007;
const ll LG=25;
ll n,m,k;
bool a[N][N];
bool b[N][N];
bool bl[N][N];
bool ur[N][N];
int sz[N*N];
int p[N*N];
bool urutox[N*N];
bool blutox[N*N];

int value(int i, int j){
    return i*(m+1)+j;
}

void make_set(int v){
    p[v]=v;
    sz[v]=1;
}

int find_set(int v){
    // cout<<v<<endl;
    if(p[v]==v)return v;
    return p[v]=find_set(p[v]);
}

void union_sets(int v, int u){
    v=find_set(v);
    u=find_set(u);
    if(u!=v){
        if(sz[v]<sz[u])swap(v,u);
        sz[v]+=sz[u];
        p[u]=v;
        sz[u]=0;
        urutox[v]|=urutox[u];
        blutox[v]|=blutox[u];
    }
}

void kpcruBL(int i, int j){
    bl[i][j]=true;
    a[i][j]=true;
    for(int jj=1;jj<=j;jj++){
        a[i][jj]=true;
        bl[i][jj]=true;
    }
    for(int ii=i;ii<=n;ii++){
        a[ii][j]=true;
        bl[ii][j]=true;
    }
}

void gnaBL(int i, int j){
    kpcruBL(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
                gnaBL(ii,jj);
            }
        }
    }
}

void kpcruUR(int i, int j){
    ur[i][j]=true;
    a[i][j]=true;
    for(int jj=j;jj<=m;jj++){
        a[i][jj]=true;
        ur[i][jj]=true;
    }
    for(int ii=1;ii<=i;ii++){
        a[ii][j]=true;
        ur[ii][j]=true;
    }
}

void gnaUR(int i, int j){
    kpcruUR(i,j);
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
                gnaUR(ii,jj);
            }
        }
    }
}

int query(int i, int j){
    bool urka=false;
    bool blka=false;
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)){
                if(ur[ii][jj])urka=true;
                if(bl[ii][jj])blka=true;
            }
        }
    }
    if(urka&&blka)return 0;
    if(urka){
        for(int ii=i-1;ii<=i+1;ii++){
            for(int jj=j-1;jj<=j+1;jj++){
                if(a[ii][jj]&&!(ii==i&&jj==j)&&!ur[ii][jj]){
                    if(urutox[find_set(value(ii,jj))])return false;
                }
            }
        }
        // cout<<"KPAV UR-in\n";
        gnaUR(i,j);
        // cout<<"TAZA UR:\n";
        // for(int i=0;i<=n+1;i++){
        //     for(int j=0;j<=m+1;j++){
        //         cout<<ur[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    if(blka){
        for(int ii=i-1;ii<=i+1;ii++){
            for(int jj=j-1;jj<=j+1;jj++){
                if(a[ii][jj]&&!(ii==i&&jj==j)&&!bl[ii][jj]){
                    if(blutox[find_set(value(ii,jj))])return false;
                }
            }
        }
        // cout<<"KPAV BL-in\n";
        gnaBL(i,j);
        // cout<<"TAZA BL:\n";
        // for(int i=0;i<=n+1;i++){
        //     for(int j=0;j<=m+1;j++){
        //         cout<<bl[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // cout<<endl;
    }
    a[i][j]=true;
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)){
                union_sets(value(i,j),value(ii,jj));
            }
        }
    }
    return 1;
}

bool used[N][N];

void dfs(int i, int j, int pi, int pj){
    used[i][j]=true;
    union_sets(value(i,j),value(pi,pj));
    for(int ii=i-1;ii<=i+1;ii++){
        for(int jj=j-1;jj<=j+1;jj++){
            if(a[ii][jj]&&!(ii==i&&jj==j)&&!used[ii][jj]){
                dfs(ii,jj,i,j);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            if(i==0||i==n+1||j==0||j==m+1){
                a[i][j]=true;
                if(i==0||j==m+1)ur[i][j]=true;
                else bl[i][j]=true;
                continue;
            }
            cin>>b[i][j];
        }
    }
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++){
            make_set(value(i,j));
            if(j==1){
                urutox[find_set(value(i,j))]=true;
            }
            if(j==m){
                blutox[find_set(value(i,j))]=true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j])query(i,j);
        }
    }
    // cout<<"OK"<<endl;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!used[i][j]&&a[i][j]){
                dfs(i,j,i,j);
            }
        }
    }
    cin>>k;
    for(int c=0;c<k;c++){
        int i,j;
        cin>>i>>j;
        cout<<query(i,j)<<endl;
    }
}

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