Submission #577509

#	Time	Username	Problem	Language	Result	Execution time	Memory
577509		AQT	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	852 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

int N, M;
bool tkn[1005][1005];
pair<int, int> dsu[1005][1005];

pair<int, int> getrt(pair<int, int> p) {
    auto q = dsu[p.first][p.second];
    if(q == p) {
        return q;
    }
    return dsu[p.first][p.second] = getrt(q);
}

void upd(int i, int j) {
    if(i >= 1 && i <= N && j >= 1 && j <= M) {
        if(!tkn[i][j]) {
            tkn[i][j] = 1;
            //cout << getrt(make_pair(i-1, j)).first << " " << getrt(make_pair(i-1, j)).second << " " << getrt(make_pair(i, j)).first << " " << getrt(make_pair(i, j)).second << "\n";
            if(tkn[i-1][j] && getrt(make_pair(i-1, j)) != getrt(make_pair(i, j))) {
                auto p = getrt(make_pair(i, j));
                dsu[p.first][p.second] = getrt(make_pair(i-1, j));
                //cout << "here" << endl;
            }
            if(tkn[i][j-1] && getrt(make_pair(i, j-1)) != getrt(make_pair(i, j))) {
                auto p = getrt(make_pair(i, j));
                dsu[p.first][p.second] = getrt(make_pair(i, j-1));
                //cout << "here" << endl;
            }
            if(tkn[i+1][j-1]) {
                upd(i+1, j);
            }
            if(tkn[i-1][j+1]) {
                upd(i, j+1);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for(int i = 0; i <= N; i++) {
        for(int j = 0; j <= M; j++) {
            dsu[i][j] = make_pair(i, j);
        }
    }
    for(int i= 1; i <= N; i++) {
        tkn[i][0] = 1;
        tkn[i][M+1] = 1;
        if(i != 1) {
            dsu[i][0] = make_pair(N, 0);
            dsu[i][M+1] = make_pair(0, M);
        }
    }
    for(int j = 1; j <= M; j++) {
        tkn[0][j] = 1;
        tkn[N+1][j] = 1;
        if(j != 1) {
            dsu[0][j] = make_pair(0, M);
            dsu[N+1][j] = make_pair(N, 0);
        }
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++) {
            cin >> tkn[i][j];
            if(tkn[i][j]) {
                tkn[i][j] = 0;
                upd(i, j);
            }
        }
    }
    int Q;
    cin >> Q;
    while(Q--) {
        int a, b;
        cin >> a >> b;
        const pair<int, int> tr = getrt(make_pair(0, M));
        const pair<int, int> bl = getrt(make_pair(N, 0));
        //cout << "pair: " << tr.first << " " << tr.second << "\n";
        //cout << "pair: " << bl.first << " " << bl.second << "\n";
        //cout << "pair: " << getrt(make_pair(a-1, b+1)).first << " " << getrt(make_pair(a-1, b+1)).second << "\n";
        if((getrt(make_pair(a-1, b)) == tr || getrt(make_pair(a-1, b+1)) == tr || getrt(make_pair(a, b+1)) == tr)
            && (getrt(make_pair(a+1, b)) == bl || getrt(make_pair(a+1, b-1)) == bl || getrt(make_pair(a, b-1)) == bl)) {
            cout << 0 << "\n";
        }
        else {
            cout << 1 << "\n";
            upd(a, b);
        }
    }
}

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