oj.uz

Submission #1065114

# Submission time Handle Problem Language Result Execution time Memory
1065114 2024-08-18T23:03:31 Z aaaaaarroz Rectangles (IOI19_rect) C++17
0 / 100
 119 ms 27868 KB 
#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=INT_MAX,r_x=0,l_y=INT_MAX,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||r_x==n||l_y==0||r_y==m){
                    continue;
                }
                if(cnt==((r_x-l_x+1)*(r_y-l_y+1))){
                    rect++;
                }
            }
        }
    }
    return rect;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 119 ms 27868 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -