Submission #366179

#	Time	Username	Problem	Language	Result	Execution time	Memory
366179		wildturtle	Furniture (JOI20_furniture)	C++14	100 / 100	3914 ms	325344 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,t;
long long A[1003][1003],fix[1000006],fix1[1000006],D[1000006],B[1000006];
set <long long> in[1000006],out[1000006];
void dfs(long long x,long long don) {
    if(fix[x]==1) return;
    fix[x]=1;
    D[x]=don;
    if(x==n*m) { fix1[x]=1; }
    for(auto to : out[x]) {
        dfs(to,don+1);
        if(fix1[to]==1) fix1[x]=1;
    }
    B[don]+=fix1[x];
}
void go_down(long long x,long long y) {
    in[x].erase(y);
    if(in[x].size()==1) return;
    B[D[x]]--;
    fix1[x]=0;
    for(auto to : out[x]) {
        go_down(to,x);
    }
}
void go_up(long long x,long long y) {
    out[x].erase(y);
    if(out[x].size()==1) return;
    B[D[x]]--;
    fix1[x]=0;
    for(auto to : in[x]) {
        go_up(to,x);
    }
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            cin>>A[i][j];
        }
    }
    for(long long i=1;i<=n;i++) {
        for(long long j=1;j<=m;j++) {
            if(j+1<=m && A[i][j]==0 && A[i][j+1]==0) {
                in[m*(i-1)+j+1].insert(m*(i-1)+j);
                out[m*(i-1)+j].insert(m*(i-1)+j+1);
            }
            if(i+1<=n && A[i][j]==0 && A[i+1][j]==0) {
                in[m*i+j].insert(m*(i-1)+j);
                out[m*(i-1)+j].insert(m*i+j);
            }   
        }
    }
    dfs(1,0);
    for(long long i=1;i<=n*m;i++) {
        //cout<<fix1[i]<<" "<<D[i]<<" "<<B[D[i]]<<endl;
        if(fix1[i]==0) {
            for(auto to : in[i]) {
                out[to].erase(i);
            }
            for(auto to : out[i]) {
                in[to].erase(i);
            }
        }
    }
    cin>>t;
    while(t--) {
        cin>>a>>b;
        a=(a-1)*m+b;
        if(fix1[a]==0) { cout<<1<<endl; continue; }
        l=0;
        if(B[D[a]+1]>out[a].size()) l=1;
        if(l==0) {
            for(auto to : out[a]) {
                if(in[to].size()==2) { l=1; break; }
            }
        }
        if(l==1) {
            cout<<1<<endl;
            fix1[a]=0; B[D[a]]--;
            for(auto to : out[a]) {
                go_down(to,a);
            }
            for(auto to : in[a]) {
                go_up(to,a);
            }
        }
        else cout<<0<<endl;
    }
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:72:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::set<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         if(B[D[a]+1]>out[a].size()) l=1;
      |            ~~~~~~~~~^~~~~~~~~~~~~~

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