oj.uz

답안 #153106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153106 2019-09-12T12:16:28 Z errorgorn Rectangles (IOI19_rect) C++14
0 / 100
 295 ms 139500 KB 
#include "rect.h"
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
int n,m;
vector<vector<int> > grid;
bool visited[2505][2505];
ii p[2505][2505];
int r[2505][2505];
int s[2505][2505];
int left [2505][2505];
int right[2505][2505];
int top[2505][2505];
int bottom[2505][2505];
ii parent(ii i){return (i==p[i.first][i.second])?i:p[i.first][i.second]=parent(p[i.first][i.second]);}
void unions(ii i, ii j){
    i=parent(i),j=parent(j);
    if (i==j) return;
    if (r[i.first][i.second]<r[j.first][j.second]){
        p[i.first][i.second]=j;
        s[j.first][j.second]+=s[i.first][i.second];
        left[j.first][j.second]=min(left[i.first][i.second],left[j.first][j.second]);
        right[j.first][j.second]=max(right[i.first][i.second],right[j.first][j.second]);
        top[j.first][j.second]=max(top[i.first][i.second],top[j.first][j.second]);
        bottom[j.first][j.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
    }
    else{
        p[j.first][j.second]=i;
        s[i.first][i.second]+=s[j.first][j.second];
        left[i.first][i.second]=min(left[i.first][i.second],left[j.first][j.second]);
        right[i.first][i.second]=max(right[i.first][i.second],right[j.first][j.second]);
        top[i.first][i.second]=max(top[i.first][i.second],top[j.first][j.second]);
        bottom[i.first][i.second]=min(bottom[i.first][i.second],bottom[j.first][j.second]);
        if (r[i.first][i.second]==r[j.first][j.second]) r[i.first][i.second]++;
    }
}
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
long long count_rectangles(vector<vector<int> > in) {
	grid=in;
	n=grid.size();
	m=grid[0].size();
	for (int x=0;x<n;x++){
        for (int y=0;y<m;y++){
            p[x][y]=ii(x,y);
            r[x][y]=0;
            s[x][y]=1;
            left[x][y]=x;
            right[x][y]=x;
            top[x][y]=y;
            bottom[x][y]=y;
        }
	}
	int xx,yy;
    for (int x=0;x<n;x++){
        for (int y=0;y<n;y++){
            if (grid[x][y]==1) continue;
            for (int z=0;z<4;z++){
                xx=x+dx[z];
                yy=y+dy[z];
                if (xx<0 || n<=xx || yy<0 || m<=yy) continue;
                if (grid[xx][yy]==0) unions(ii(x,y),ii(xx,yy));
            }
        }
    }
    ii temp;
    long long ans=0;
    for (int x=1;x<n-1;x++){
        for (int y=1;y<m-1;y++){
            if (grid[x][y]==1) continue;
            temp=parent(ii(x,y));
            xx=temp.first;
            yy=temp.second;
            if (visited[xx][yy]) continue;
            visited[xx][yy]=true;
            if (left[xx][yy]==0 || right[xx][yy]==n-1 || bottom[xx][yy]==0 || top[xx][yy]==m-1) continue;
            if ((right[xx][yy]-left[xx][yy]+1)*(top[xx][yy]-bottom[xx][yy]+1)==s[xx][yy]) ans++;
        }
    }
    return ans;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Incorrect 3 ms 632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Incorrect 295 ms 139500 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -