제출 #1237181

#제출 시각아이디문제언어결과실행 시간메모리
1237181MuhammadSaramRectangles (IOI19_rect)C++20
13 / 100
488 ms549580 KiB
#include "rect.h" #include <bits/stdc++.h> using namespace std; const int M = 2500*2500; int col[M], mn[M][2], mx[M][2]; vector<int> ver[M]; void add(int u,int v) { u=col[u], v=col[v]; if (u==v) return; if (ver[u].size()<ver[v].size()) swap(u,v); for (int i:ver[v]) col[i]=u, ver[u].push_back(i); for (int j=0;j<2;j++) mn[u][j]=min(mn[u][j],mn[v][j]), mx[u][j]=max(mx[u][j],mx[v][j]); ver[v].clear(); } long long count_rectangles(vector<vector<int>> a) { int n=a.size(), m=a[0].size(); for (int i=0;i<n;i++) for (int j=0;j<m;j++) if (!a[i][j]) col[i*m+j]=i*m+j, mn[i*m+j][0]=mx[i*m+j][0]=i, mn[i*m+j][1]=mx[i*m+j][1]=j, ver[i*m+j]={i*m+j}; for (int i=0;i<n;i++) for (int j=0;j<m;j++) { if (a[i][j]) continue; if (i && !a[i-1][j]) add(i*m+j-m,i*m+j); if (j && !a[i][j-1]) add(i*m+j-1,i*m+j); } int ans=0; for (int i=1;i<n-1;i++) for (int j=1;j<m-1;j++) { int ar=(mx[i*m+j][0]-mn[i*m+j][0]+1)*(mx[i*m+j][1]-mn[i*m+j][1]+1); if (ar==ver[i*m+j].size() && min(mn[i*m+j][0],mn[i*m+j][1]) && mx[i*m+j][0]<n-1 && mx[i*m+j][1]<m-1) ans++; } return ans; }
#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...