Submission #722997

#	Time	Username	Problem	Language	Result	Execution time	Memory
722997		Darren0724	Rectangles (IOI19_rect)	C++17	13 / 100	1274 ms	246092 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define fs first
#define sc second
vector<vector<int>> v,sz,l,r,u,d;
vector<vector<pair<int,int>>> pa;
pair<int,int> Find(int a,int b){
    if(pa[a][b]==make_pair(a,b)){
        return {a,b};
    }
    pair<int,int> p=Find(pa[a][b].fs,pa[a][b].sc);
    return pa[a][b]=p;
}
void onion(pair<int,int> a,pair<int,int> b){
    //cout<<"ok"<<endl;
    a=Find(a.fs,a.sc),b=Find(b.fs,b.sc);
    if(a==b){
        return;
    }
    /*if(sz[a.fs][a.sc]>sz[b.fs][b.sc]){
        swap(a,b);
    }*/
    sz[b.fs][b.sc]+=sz[a.fs][a.sc];
    pa[a.fs][a.sc]=b;
    l[b.fs][b.sc]=min(l[a.fs][a.sc],l[b.fs][b.sc]);
    r[b.fs][b.sc]=max(r[a.fs][a.sc],r[b.fs][b.sc]);
    u[b.fs][b.sc]=min(u[a.fs][a.sc],u[b.fs][b.sc]);
    d[b.fs][b.sc]=max(d[a.fs][a.sc],d[b.fs][b.sc]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n=a.size();
	int m=a[0].size();
    v.resize(n+2,vector<int>(m+2,-1));
    pa.resize(n+2,vector<pair<int,int>>(m+2));
    sz.resize(n+2,vector<int>(m+2,1));
    l=r=u=d=sz;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            v[i][j]=a[i-1][j-1];
            pa[i][j]={i,j};
            l[i][j]=r[i][j]=j;
            u[i][j]=d[i][j]=i;
        }
    }
    vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //cout<<i<<' '<<j<<endl;
            for(int k=0;k<4;k++){
                int i1=i+dx[k];
                int j1=j+dy[k];
                if(v[i][j]==0&&v[i1][j1]==0){
                    //cout<<i<<' '<<j<<' '<<i1<<' '<<j1<<endl;
                    onion(make_pair(i,j),make_pair(i1,j1));
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(v[i][j]==1){
                continue;
            }
            if(make_pair(i,j)!=Find(i,j)){
                continue;
            }
            if(u[i][j]==1||d[i][j]==n||l[i][j]==1||r[i][j]==m){
                continue;
            }
            //cout<<i<<' '<<j<<endl;
            int need=(r[i][j]-l[i][j]+1)*(d[i][j]-u[i][j]+1);
            if(sz[i][j]==need){
                ans++;
            }
        }
    }


    return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
/*
5 5
0 0 1 1 0
0 1 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
*/

• 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