Submission #1065120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065120		aaaaaarroz	Rectangles (IOI19_rect)	C++17	13 / 100	259 ms	62584 KiB

rect

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool limites(int n, int m, int x, int y){
    return x>=0&&x<n&&y>=0&&y<m;
}
ll count_rectangles(const vector<vector<int>>a) {
    ll rect=0;
    int n = a.size();
    int m = a[0].size();
    vector<vector<bool>>v(n,vector<bool>(m));
    vector<int>dx={0,-1,0,1};
    vector<int>dy={1,0,-1,0};
    for(int i=1;i<n-1;i++){
        for(int j=1;j<m-1;j++){
            if(!v[i][j]&&a[i][j]==0){
                v[i][j]=true;
                queue<pair<int,int>>cola;
                cola.push({i,j});
                int l_x=n,r_x=0,l_y=m,r_y=0;
                int cnt=0;
                while(!cola.empty()){
                    pair<int,int>nodo=cola.front();
                    cola.pop();
                    l_x=min(l_x,nodo.first);
                    r_x=max(r_x,nodo.first);
                    l_y=min(l_y,nodo.second);
                    r_y=max(r_y,nodo.second);
                    cnt++;
                    for(int i=0;i<4;i++){
                        int x=nodo.first+dx[i],y=nodo.second+dy[i];
                        if(limites(n,m,x,y)){
                            if(a[x][y]==0){
                                if(!v[x][y]){
                                    v[x][y]=true;
                                    cola.push({x,y});
                                }
                            }
                        }
                    }
                }
                if(l_x==0)continue;
                if(r_x==n-1)continue;
                if(l_y==0)continue;
                if(r_y==m-1)continue;
                if(cnt==((r_x-l_x+1)*(r_y-l_y+1))){
                    rect++;
                }
            }
        }
    }
    return rect;
}

• 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