oj.uz

Submission #499064

# Submission time Handle Problem Language Result Execution time Memory
499064 2021-12-27T07:25:16 Z khoabright Furniture (JOI20_furniture) C++17
100 / 100
 278 ms 19968 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()

const int N = 1005;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

int id[N][N], R[N][N], vst[N][N];
int cnt[2 * N];
int n, m;

void dfs(int x, int y) {
    if (vst[x][y]) return;
    vst[x][y] = 1;
    if (R[x][y] == 1) return;
    if (x == n && y == m) {
        R[x][y] = 0;
        ++cnt[x + y];
        return;
    }

    R[x][y] = 1;
    rep(k, 0, 1) {
        int xx = x + dx[k];
        int yy = y + dy[k];
        if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
        dfs(xx, yy);
        R[x][y] &= R[xx][yy];
    }
    //cout<<"x,y,x+y,cnt,R="<<x<<' '<<y<<' '<<x+y<<' '<<cnt[x+y]<<' '<<R[x][y]<<'\n';
    cnt[x + y] += (R[x][y] == 0);
}

void update(int x, int y) {
   // cout<<"x,y="<<x<<' '<<y<<'\n';
    rep(k, 0, 3) {
        int xx = x + dx[k];
        int yy = y + dy[k];

        if (xx < 1 || xx > n || yy < 1 || yy > m || R[xx][yy] == 1 || (xx == n && yy == m) || (xx == 1 && yy == 1)) continue;
        if (R[xx - 1][yy] && R[xx][yy - 1]) {
            R[xx][yy] = 1;
        }
        if (R[xx + 1][yy] && R[xx][yy + 1]) {
            R[xx][yy] = 1;
        }
        if (R[xx][yy]) {
            --cnt[xx + yy];
            update(xx, yy);
        }
    }
}

void solve() {
    cin >> n >> m;
    rep(i, 0, N - 1) rep(j, 0, N - 1) R[i][j] = 1;
    rep(x, 1, n) rep(y, 1, m) {
        cin >> R[x][y];
        if (R[x][y] == 0) R[x][y] = 2;
    }
    dfs(1, 1);
    rep(x, 1, n) rep(y, 1, m) if (R[x][y] == 2) R[x][y] = 1;
//    cout<<'\n';
//    rep(i, 1, n)  rep(j, 1, m){
//        cout << R[i][j]<<" \n"[j == m];
//    }

    int q; cin >> q;
    while (q--) {
//                cout<<'\n';
//    rep(i, 1, n)  rep(j, 1, m){
//        cout << R[i][j]<<" \n"[j == m];
//    }

        int x, y; cin >> x >> y;
        //cout << "R,cnt="<<R[x][y]<<' '<<cnt[x+y]<<'\n';
        if (R[x][y] == 1) {
            cout << "1\n";
            continue;

        }
        if (cnt[x + y] <= 1) {
            cout << "0\n";
            continue;
        }

        cout << "1\n";
        R[x][y] = 1;
        --cnt[x + y];
        update(x, y);

//            cout<<'\n';
//    rep(i, 1, n)  rep(j, 1, m){
//        cout << R[i][j]<<" \n"[j == m];
//    }

    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 4 ms 4684 KB Output is correct
4 Correct 5 ms 4732 KB Output is correct
5 Correct 4 ms 4684 KB Output is correct
6 Correct 6 ms 4684 KB Output is correct
7 Correct 4 ms 4684 KB Output is correct
8 Correct 5 ms 4684 KB Output is correct
9 Correct 4 ms 4684 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 4 ms 4684 KB Output is correct
3 Correct 4 ms 4684 KB Output is correct
4 Correct 5 ms 4732 KB Output is correct
5 Correct 4 ms 4684 KB Output is correct
6 Correct 6 ms 4684 KB Output is correct
7 Correct 4 ms 4684 KB Output is correct
8 Correct 5 ms 4684 KB Output is correct
9 Correct 4 ms 4684 KB Output is correct
10 Correct 9 ms 4812 KB Output is correct
11 Correct 4 ms 4556 KB Output is correct
12 Correct 125 ms 12868 KB Output is correct
13 Correct 60 ms 10012 KB Output is correct
14 Correct 270 ms 17564 KB Output is correct
15 Correct 262 ms 17820 KB Output is correct
16 Correct 243 ms 18716 KB Output is correct
17 Correct 250 ms 19492 KB Output is correct
18 Correct 234 ms 19104 KB Output is correct
19 Correct 244 ms 19968 KB Output is correct
20 Correct 238 ms 19932 KB Output is correct
21 Correct 278 ms 19908 KB Output is correct