oj.uz

Submission #683942

# Submission time Handle Problem Language Result Execution time Memory
683942 2023-01-19T17:26:36 Z alvingogo Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 1928 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 340 KB Output is correct
2 Correct 102 ms 456 KB Output is correct
3 Correct 244 ms 564 KB Output is correct
4 Correct 433 ms 644 KB Output is correct
5 Correct 458 ms 656 KB Output is correct
6 Correct 531 ms 828 KB Output is correct
7 Correct 393 ms 684 KB Output is correct
8 Correct 349 ms 692 KB Output is correct
9 Correct 363 ms 676 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 340 KB Output is correct
2 Correct 102 ms 456 KB Output is correct
3 Correct 244 ms 564 KB Output is correct
4 Correct 433 ms 644 KB Output is correct
5 Correct 458 ms 656 KB Output is correct
6 Correct 531 ms 828 KB Output is correct
7 Correct 393 ms 684 KB Output is correct
8 Correct 349 ms 692 KB Output is correct
9 Correct 363 ms 676 KB Output is correct
10 Execution timed out 5026 ms 1928 KB Time limit exceeded
11 Halted 0 ms 0 KB -