oj.uz

Submission #365038

# Submission time Handle Problem Language Result Execution time Memory
365038 2021-02-10T19:50:56 Z giorgikob Furniture (JOI20_furniture) C++14
100 / 100
 3343 ms 300904 KB 
#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(){
    ios::sync_with_stdio(0);
    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

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

# Verdict Execution time Memory Grader output
1 Correct 68 ms 96748 KB Output is correct
2 Correct 71 ms 96364 KB Output is correct
3 Correct 75 ms 96876 KB Output is correct
4 Correct 85 ms 97132 KB Output is correct
5 Correct 87 ms 97260 KB Output is correct
6 Correct 92 ms 97804 KB Output is correct
7 Correct 91 ms 97772 KB Output is correct
8 Correct 90 ms 97772 KB Output is correct
9 Correct 94 ms 97772 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 96748 KB Output is correct
2 Correct 71 ms 96364 KB Output is correct
3 Correct 75 ms 96876 KB Output is correct
4 Correct 85 ms 97132 KB Output is correct
5 Correct 87 ms 97260 KB Output is correct
6 Correct 92 ms 97804 KB Output is correct
7 Correct 91 ms 97772 KB Output is correct
8 Correct 90 ms 97772 KB Output is correct
9 Correct 94 ms 97772 KB Output is correct
10 Correct 146 ms 104556 KB Output is correct
11 Correct 80 ms 97388 KB Output is correct
12 Correct 1562 ms 267464 KB Output is correct
13 Correct 500 ms 234988 KB Output is correct
14 Correct 2779 ms 259516 KB Output is correct
15 Correct 3007 ms 269704 KB Output is correct
16 Correct 2957 ms 284468 KB Output is correct
17 Correct 3229 ms 294764 KB Output is correct
18 Correct 3228 ms 289772 KB Output is correct
19 Correct 3213 ms 300856 KB Output is correct
20 Correct 3343 ms 300904 KB Output is correct
21 Correct 3274 ms 300780 KB Output is correct