Submission #443349

#TimeUsernameProblemLanguageResultExecution timeMemory
443349mkisicRectangles (IOI19_rect)C++14
0 / 100
452 ms98344 KiB
#include "rect.h" #include <queue> #include <cassert> #include <iostream> #include <cstring> #include <vector> #include <algorithm> using namespace std; typedef pair <int, int> pii; #define TRACE(x) cerr << #x << ' ' << x << endl #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define REP(i, n) FOR(i, 0, n) #define _ << " " << #define fi first #define sec second #define pb push_back const int MAXN = 2501; const int smjerx[] = {1, -1, 0, 0}; const int smjery[] = {0, 0, 1, -1}; int p[MAXN][MAXN]; int bio[MAXN][MAXN]; int n, m; bool bfs(int X, int Y) { queue <int> q; q.push(X); q.push(Y); bio[X][Y] = 1; int maxX = X; int maxY = Y; int minX = X; int minY = Y; int rub = 0; int cnt = 0; while (!q.empty()) { int x = q.front(); q.pop(); int y = q.front(); q.pop(); maxX = max(maxX, x); maxY = max(maxY, y); minX = min(minX, x); minY = min(minY, y); cnt++; if (x == 0 || x == n - 1 || y == 0 || y == m - 1) rub++; REP(i, 4) { int nx = x + smjerx[i]; int ny = y + smjery[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= m || bio[nx][ny] || p[nx][ny]) continue; bio[nx][ny] = 1; q.push(nx); q.push(ny); } } return (rub == 0) && (maxX - minX + 1) * (maxY - minY + 1) == cnt; } long long solve1() { int ret = 0; REP(i, n) REP(j, m) { if (bio[i][j] || p[i][j]) continue; ret += bfs(i, j); } return ret; } long long count_rectangles(std::vector<std::vector<int> > a) { n = a.size(); m = a[0].size(); REP(i, n) REP(j, m) p[i][j] = a[i][j]; int maks = 0; REP(i, n) REP(j, m) maks = max(maks, p[i][j]); if (maks == 1) return solve1(); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...