Submission #1203845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203845		Aviansh	Rectangles (IOI19_rect)	C++20	0 / 100	80 ms	23112 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>

using namespace std;

int mxi,mxj,mni,mnj;

void dfs(int x, int y, vector<vector<int>>&a,vector<vector<bool>> &vis){
    int n=a.size();
    int m=a[0].size();
    if(x<0||x>=n||y<0||y>=m)
        return;
    if(a[x][y])
        return;
    if(vis[x][y])
        return;
    mxi=max(mxi,x);
    mxj=max(mxj,y);
    mni=min(mni,x);
    mnj=min(mxj,y);
    vis[x][y]=1;
    dfs(x+1,y,a,vis);
    dfs(x-1,y,a,vis);
    dfs(x,y-1,a,vis);
    dfs(x,y+1,a,vis);
}

long long count_rectangles(vector<vector<int>> a) {
    int n=a.size();
    int m=a[0].size();
    if(n<3||m<3)
        return 0;
    long long ans = 0;
    vector<vector<bool>>vis(n,vector<bool>(m,0));
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(a[i][j]||vis[i][j]){
                continue;
            }
            mxi=i;
            mni=i;
            mxj=j;
            mnj=j;
            dfs(i,j,a,vis);
            if(mni==0||mxi==n-1||mnj==0||mxj==m-1){
                continue;
            }
            bool wor = 1;
            for(int i = mni;i<=mxi;i++){
                for(int j = mnj;j<=mxj;j++){
                    if(a[i][j]){
                        wor=0;
                        goto cont;
                    }
                }
            }
            cont:
                ans+=wor;
        }
    }
    return ans;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28