제출 #1212461

#제출 시각아이디문제언어결과실행 시간메모리
1212461guagua0407Rectangles (IOI19_rect)C++20
13 / 100
1338 ms303988 KiB
#include "rect.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; namespace{ struct DSU{ vector<int> e; vector<int> mnx,mny,mxx,mxy; DSU(int n){ e=vector<int>(n,-1); mnx=mny=mxx=mxy=vector<int>(n); } void go(int i,int x,int y){ mnx[i]=mxx[i]=x; mny[i]=mxy[i]=y; } int find(int x){ return (e[x]<0?x:e[x]=find(e[x])); } bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(e[a]>e[b]) swap(a,b); e[a]+=e[b]; e[b]=a; mnx[a]=min(mnx[a],mnx[b]); mny[a]=min(mny[a],mny[b]); mxx[a]=max(mxx[a],mxx[b]); mxy[a]=max(mxy[a],mxy[b]); return true; } }; } long long count_rectangles(std::vector<std::vector<int> > a) { int n=(int)a.size(); int m=(int)a[0].size(); vector<pair<int,pair<int,int>>> vec; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ vec.push_back({a[i][j],{i,j}}); } } sort(all(vec)); vector<vector<bool>> active(n,vector<bool>(m)); DSU dsu(n*m); vector<bool> used(n*m); ll ans=0; auto ok=[&](int i){ ll sz=-dsu.e[i]; ll sz2=1ll*(dsu.mxx[i]-dsu.mnx[i]+1)*(dsu.mxy[i]-dsu.mny[i]+1); return (sz==sz2 and dsu.mnx[i]!=0 and dsu.mxx[i]!=n-1 and dsu.mny[i]!=0 and dsu.mxy[i]!=m-1); }; for(int pos=0;pos<n*m;){ int cur=vec[pos].f; vector<int> st; while(pos<n*m and vec[pos].f==cur){ auto [x,y]=vec[pos].s; dsu.go(x*m+y,x,y); active[x][y]=true; for(int k=0;k<4;k++){ int nx=x+dx[k]; int ny=y+dy[k]; if(nx<0 or nx>=n or ny<0 or ny>=m or !active[nx][ny]) continue; dsu.unite(x*m+y,nx*m+ny); } st.push_back(x*m+y); pos++; } vector<int> st2; for(auto v:st){ int i=dsu.find(v); if(used[i]) continue; used[i]=true; st2.push_back(i); if(ok(i)){ //cout<<cur<<' '<<i/m+1<<' '<<i%m+1<<'\n'; ans++; } } for(auto v:st2){ used[v]=false; } } 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...