Submission #683942

#	Time	Username	Problem	Language	Result	Execution time	Memory
683942		alvingogo	Furniture (JOI20_furniture)	C++14	5 / 100	5026 ms	1928 KiB

furniture

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct DSU{
    vector<int> bo,ss;
    vector<int> st;
    void init(int n){
        bo.resize(n);
        iota(bo.begin(),bo.end(),0);
        ss.resize(n,1);
    }
    int find(int x){
        return bo[x]==x?x:find(bo[x]);
    }
    int merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y){
            return 0;
        }
        if(ss[x]>ss[y]){
            swap(x,y);
        }
        st.push_back(x);
        bo[x]=y;
        ss[y]+=ss[x];
        return 1;
    }
    void undo(){
        auto h=st.back();
        st.pop_back();
        ss[bo[h]]-=ss[h];
        bo[h]=h;
    }
}dsu;
int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    vector<pair<int,int> > g;
    dsu.init(n*m+4);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int a;
            cin >> a;
            if(a){
                g.push_back({i,j});
            }
        }
    }
    int q;
    cin >> q;
    int u=g.size();
    for(int i=0;i<q;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        g.push_back({a,b});
    }
    vector<int> ans;
    const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
    vector<vector<int> > v(n,vector<int>(m));
    for(auto h:g){
        v[h.fs][h.sc]=1;
        vector<vector<int> > dp(n,vector<int>(m));
        dp[0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!v[i][j] && i+1<n){
                    dp[i+1][j]|=dp[i][j];
                }
                if(!v[i][j] && j+1<m){
                    dp[i][j+1]|=dp[i][j];
                }
            }
        }
        if(dp[n-1][m-1]){
            ans.push_back(1);
        }
        else{
            ans.push_back(0);
            v[h.fs][h.sc]=0;
        }
        /*
        int cnt=0;
        for(int k=0;k<8;k++){
            int x=h.fs+dx[k],y=h.sc+dy[k];
            if(x>=0 && x<n && y>=0 && y<m){
                if(v[x][y]){
                    cnt+=dsu.merge(h.fs*m+h.sc,x*m+y);
                }
            }
            if(x<0){
                cnt+=dsu.merge(h.fs*m+h.sc,n*m);
            }
            if(y<0){
                cnt+=dsu.merge(h.fs*m+h.sc,n*m+1);
            }
            if(x>=n){
                cnt+=dsu.merge(h.fs*m+h.sc,n*m+2);
            }
            if(x>=m){
                cnt+=dsu.merge(h.fs*m+h.sc,n*m+3);
            }
        }
        if(dsu.find(n*m)==dsu.find(n*m+2) || dsu.find(n*m+1)==dsu.find(n*m+3)){
            for(int j=0;j<cnt;j++){
                dsu.undo();
            }
            ans.push_back(0);
        }
        else{
            ans.push_back(1);
            v[h.fs][h.sc]=1;
        }
        */
    }
    for(int i=u;i<u+q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:67:15: warning: unused variable 'dx' [-Wunused-variable]
   67 |     const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
      |               ^~
furniture.cpp:67:42: warning: unused variable 'dy' [-Wunused-variable]
   67 |     const int dx[8]={1,1,1,0,-1,-1,-1,0},dy[8]={-1,0,1,1,1,0,-1,-1};
      |                                          ^~

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