Submission #405658

#	Time	Username	Problem	Language	Result	Execution time	Memory
405658		Tc14	Rectangles (IOI19_rect)	C++17	13 / 100	395 ms	61656 KiB

rect

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;

ll count_rectangles(ve<ve<int>> A) {

    int n, m;
    ll ans;
    ve<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
    queue<pii> Q;

    n = (int)A.size();
    m = (int)A[0].size();

    ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (A[i][j] == 0) {

                Q.push({i, j});
                A[i][j] = -1;

                int xMin = i;
                int xMax = i;
                int yMin = j;
                int yMax = j;
                int cnt = 1;

                while (!Q.empty()) {
                    int x, y;
                    tie(x, y) = Q.front();
                    Q.pop();

                    for (int k = 0; k < 4; k++) {
                        int xNew = x + dx[k];
                        int yNew = y + dy[k];

                        if (0 <= xNew && xNew < n && 0 <= yNew && yNew < m) {
                            if (A[xNew][yNew] == 0) {

                                Q.push({xNew, yNew});
                                A[xNew][yNew] = -1;

                                xMin = min(xMin, xNew);
                                xMax = max(xMax, xNew);
                                yMin = min(yMin, yNew);
                                yMax = max(yMax, yNew);
                                cnt++;
                            }
                        }
                    }
                }

                if (xMin != 0 && xMax != n - 1 && yMin != 0 && yMax != m - 1) {
                    if ((xMax - xMin + 1) * (yMax - yMin + 1) == cnt) ans++;
                }
            }
        }
    }

	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