Submission #365037

#	Time	Username	Problem	Language	Result	Execution time	Memory
365037		giorgikob	Furniture (JOI20_furniture)	C++14	100 / 100	3845 ms	310420 KiB

furniture

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e3+5;

int n,m;
int A[N][N];
set<int>in[N*N],out[N*N];
int fix[N*N];
int x,a,b;
int H[N*N],cnt[N*N],can[N*N];

void erase_vertex(int x){
    //cout << x << " ----" << endl;
    for(auto to : out[x]){
        in[to].erase(x);//cout << x << " " << to << endl;
    }

    for(auto to : in[x]){
        out[to].erase(x); //cout << to << " " << x << endl;
    }
    //cout << "----" << endl;
}


void add_edge(int x,int y){
    out[x].insert(y); in[y].insert(x);
    out[x].insert(y); in[y].insert(x);
}

void dfs(int x,int h){
    //cout << x << endl;
    fix[x] = 1;
    H[x] = h;

    if(x == n*m){
        can[x] = 1;
        cnt[h]++;
        return ;
    }

    for(auto to : out[x]){
        if(fix[to] == 0)
        dfs(to,h+1);
        can[x] |= can[to];
    }

    cnt[h] += can[x];
}

bool check(int x){
    if(cnt[H[x]+1] > out[x].size()) return true;

    for(auto to : out[x]){
        if(in[to].size() == 2) return true;
    }

    return false;
}

void go_down(int x,int p){
    in[x].erase(p);
    if(in[x].size() == 1) return ;
    cnt[H[x]]--;
    can[x] = 0;
    for(auto to : out[x]){
        go_down(to,x);
    }
}

void go_up(int x,int p){
    out[x].erase(p);
    if(out[x].size() == 1) return ;
    cnt[H[x]]--;
    can[x] = 0;
    for(auto to : in[x]){
        go_up(to,x);
    }
}

int main(){

    cin >> n >> m;
    int a = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> A[i][j];
         }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            a++;
            if(!A[i][j] && !A[i][j+1] && j+1 <= m)add_edge(a,a+1);
            if(!A[i][j] && !A[i+1][j] && i+1 <= n)add_edge(a,a+m);
         }
    }

    //cout << 1 << endl;
    dfs(1,0);

    for(int i = 1; i <= n*m; i++) if(can[i] == 0) erase_vertex(i);

    int q;
    cin >> q;
    while(q--){
        cin >> a >> b;
        x = (a-1)*m+b;
        if(can[x] == 0){
            cout << 1 << endl;
            continue;
        }


        if(check(x)){
            cout << 1 << endl;
            can[x] = 0; cnt[H[x]]--;
            for(auto to : out[x])go_down(to,x);
            for(auto to : in[x])go_up(to,x);
        } else {
            cout << 0 << endl;
        }
    }
}

Compilation message (stderr)

furniture.cpp: In function 'bool check(int)':
furniture.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if(cnt[H[x]+1] > out[x].size()) return true;
      |        ~~~~~~~~~~~~^~~~~~~~~~~~~~~

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