Submission #610767

#	Time	Username	Problem	Language	Result	Execution time	Memory
610767		lorenzoferrari	Rectangles (IOI19_rect)	C++17	13 / 100	344 ms	62540 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

#define UP 0
#define LEFT 1
#define DOWN 2
#define RIGHT 3

constexpr int INF = 1e9;

const vector<array<int, 2>> dd{{0,1},{0,-1},{1,0},{-1,0}};

int n, m;

struct comp {
    int sz;
    array<int, 4> ext;
    comp() : sz(0), ext({INF, INF, -INF, -INF}) {}
    comp(int i, int j) : sz(1), ext({i,j,i,j}) {}
    bool good() {
        if (ext[UP] == 0 || ext[DOWN] == n-1) return false;
        if (ext[LEFT] == 0 || ext[RIGHT] == m-1) return false;
        return sz == (ext[DOWN] - ext[UP] + 1) * (ext[RIGHT] - ext[LEFT] + 1);
    }
};
comp join(const comp& a, const comp& b) {
    comp ans;
    ans.sz = a.sz + b.sz;
    ans.ext[UP] = min(a.ext[UP], b.ext[UP]);
    ans.ext[LEFT] = min(a.ext[LEFT], b.ext[LEFT]);
    ans.ext[DOWN] = max(a.ext[DOWN], b.ext[DOWN]);
    ans.ext[RIGHT] = max(a.ext[RIGHT], b.ext[RIGHT]);
    return ans;
}

LL count_rectangles(vector<vector<int>> a) {
    n = a.size();
    m = a[0].size();


    // subtask a[i][j] \in {0,1}
    
    LL ans = 0;
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
        if (vis[i][j] || a[i][j] == 1) continue;
        comp cur(i, j);
        queue<array<int, 2>> Q;
        Q.push({i, j});
        vis[i][j] = true;
        while (!Q.empty()) {
            auto [x, y] = Q.front();
            Q.pop();
            for (auto [dx, dy] : dd) {
                int nx = x + dx;
                int ny = y + dy;
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (vis[nx][ny] || a[nx][ny] == 1) continue;
                vis[nx][ny] = true;
                Q.push({nx, ny});
                cur = join(cur, comp(nx, ny));
            }
        }
        ans += cur.good();
    }
    
    return ans;
}

• 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