Submission #1212583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212583		loiiii12358	Rectangles (IOI19_rect)	C++20	13 / 100	391 ms	196336 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> roots,cnt,r,c,R,C;

int find_root(int u){
    if(u==roots[u]){
        return u;
    }
    return roots[u]=find_root(roots[u]);
}

void merge(int u,int v){
    u=find_root(u);
    v=find_root(v);
    if(u!=v){
        roots[u]=v;
        cnt[v]+=cnt[u];
        r[v]=min(r[v],r[u]);
        R[v]=max(R[v],R[u]);
        c[v]=min(c[v],c[u]);
        C[v]=max(C[v],C[u]);
    }
}

long long count_rectangles(vector<vector<int> > a) {
	int n=a.size(),m=a[0].size();
    roots.resize(n*m);cnt.resize(n*m);r.resize(n*m);c.resize(n*m);R.resize(n*m);C.resize(n*m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            roots[i*m+j]=i*m+j;
            cnt[i*m+j]=1;
            r[i*m+j]=R[i*m+j]=i;
            c[i*m+j]=C[i*m+j]=j;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==0){
                if(i>0&&a[i-1][j]==0){
                    merge(i*m+j,(i-1)*m+j);
                }
                if(i<n-1&&a[i+1][j]==0){
                    merge(i*m+j,(i+1)*m+j);
                }
                if(j>0&&a[i][j-1]==0){
                    merge(i*m+j,i*m+j-1);
                }
                if(j<m-1&&a[i][j+1]==0){
                    merge(i*m+j,i*m+j+1);
                }
            }
        }
    }
    long long ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(find_root(i*m+j)==i*m+j&&a[i][j]==0){
                if(r[i*m+j]==0||R[i*m+j]==n-1||c[i*m+j]==0||C[i*m+j]==m-1){
                    continue;
                }else if((R[i*m+j]-r[i*m+j]+1)*(C[i*m+j]-c[i*m+j]+1)==cnt[i*m+j]){
                    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