Submission #1211934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211934		ProtonDecay314	Rectangles (IOI19_rect)	C++20	13 / 100	704 ms	208028 KiB

rect

/*
Uses UFDS

Note: valid exactly when it satisfies:
(1) area condition
(2) no border condition (i.e., the max/min x and y of the component is within the bounds)
*/
#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;

struct UF {
    int c, n;
    vi par, csize, minx, maxx, miny, maxy;

    UF(int y, int x): c(x), n(x * y), par(x * y, 0), csize(x * y, 1), minx(x * y, 2500), maxx(x * y, 0), miny(x * y, 2500), maxy(x * y, 0) {
        for(int i = 0; i < n; i++) {
            par[i] = i;
        }

        for(int j = 0; j < y; j++) {
            for(int i = 0; i < x; i++) {
                int cid = coord(j, i);
                minx[cid] = i;
                maxx[cid] = i;
                miny[cid] = j;
                maxy[cid] = j;
            }
        }
    }; 

    int coord(int y, int x) {
        return y * c + x;
    }

    int find(int y, int x) {
        int c_coord = coord(y, x);
        return find(c_coord);
    }

    int find(int i) {
        return (i == par[i] ? i : par[i] = find(par[i]));
    }

    bool conn(int y1, int x1, int y2, int x2) {
        return find(y1, x1) == find(y2, x2);
    }

    void unify(int y1, int x1, int y2, int x2) {
        int pari = find(y1, x1), parj = find(y2, x2);

        if(pari == parj) return;

        int new_minx = min(minx[pari], minx[parj]);
        int new_maxx = max(maxx[pari], maxx[parj]);
        int new_miny = min(miny[pari], miny[parj]);
        int new_maxy = max(maxy[pari], maxy[parj]);

        int new_csize = csize[pari] + csize[parj];

        if(csize[pari] < csize[parj]) {
            // i into j
            par[pari] = parj;

            csize[parj] = new_csize;
            minx[parj] = new_minx;
            maxx[parj] = new_maxx;
            miny[parj] = new_miny;
            maxy[parj] = new_maxy;
        } else {
            par[parj] = pari;

            csize[pari] = new_csize;
            minx[pari] = new_minx;
            maxx[pari] = new_maxx;
            miny[pari] = new_miny;
            maxy[pari] = new_maxy;
        }
    }
};

ll count_rectangles(vvi a) {
    int rows = a.size(), cols = a[0].size();

    UF uf(rows, cols);

    for(int y = 0; y < rows; y++) {
        for(int x = 0; x < cols; x++) {
            if(a[y][x] == 1) continue;
            if(x < cols - 1 && a[y][x + 1] == 0) uf.unify(y, x, y, x + 1);
            if(y < rows - 1 && a[y + 1][x] == 0) uf.unify(y, x, y + 1, x);
        }
    }

    set<int> good_comps;

    for(int y = 1; y < rows - 1; y++) {
        for(int x = 1; x < cols - 1; x++) {
            int cid = uf.find(y, x);

            if(a[y][x] == 1) continue;

            if(uf.minx[cid] == 0 || uf.maxx[cid] == cols - 1 || uf.miny[cid] == 0 || uf.maxy[cid] == rows - 1) continue;

            if(good_comps.count(cid) > 0) continue;

            if((uf.maxx[cid] - uf.minx[cid] + 1) * (uf.maxy[cid] - uf.miny[cid] + 1) == uf.csize[cid]) good_comps.insert(cid);
        }
    }

	return good_comps.size();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28