QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#395729#6746. Merge the RectanglesGaomerWA 757ms153660kbC++142.8kb2024-04-21 17:50:002024-04-21 17:50:00

Judging History

你现在查看的是最新测评结果

  • [2024-04-21 17:50:00]
  • 评测
  • 测评结果:WA
  • 用时:757ms
  • 内存:153660kb
  • [2024-04-21 17:50:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int input(){
    char ch=getchar();
    int v=0,sign=1;
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')sign=-sign;
    for(;isdigit(ch);ch=getchar())
        v=(v<<3)+(v<<1)+(ch^'0');
    return v*sign;
}
const int nm=1504;
bool vis[nm][nm];
char ud[nm][nm],lr[nm][nm];
int n,m,tt,ans,u,d,l,r;
struct rec{int u,d,l,r;}x[nm*nm];
void dfs(int i,int j){
    if(vis[i][j])return ;
    vis[i][j]=true;
    u=min(u,i),d=max(d,i);
    l=min(l,j),r=max(r,j);
    if(lr[i][j-1]=='0')dfs(i,j-1);
    if(lr[i][j]=='0')dfs(i,j+1);
    if(ud[i-1][j]=='0')dfs(i-1,j);
    if(ud[i][j]=='0')dfs(i+1,j);
}
map<int,int>hor[nm][2],ver[nm][2];
void erase(int i){
    int u=x[i].u,d=x[i].d,l=x[i].l,r=x[i].r;
    hor[u][1].erase(l),hor[d][0].erase(l);
    ver[l][1].erase(u),ver[r][0].erase(u);
}
int main(){
    n=input(),m=input();
    for(int i=1;i<n;i++)
        scanf("%s",ud[i]+1);
    for(int i=1;i<=n;i++)
        scanf("%s",lr[i]+1);
//    for(int i=1;i<n;i++){
//        for(int j=1;j<=m;j++)
//            cout<<ud[i][j];
//            cout<<endl;
//    }
//    return 0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!vis[i][j]){
                u=d=i,l=r=j;
                dfs(i,j),l--,u--;
                while(true){
                    int last=0;
                    if(ver[l][0].find(u)!=ver[l][0].end()){
                        last=ver[l][0][u];
                        if(x[last].d==d){
                            l=x[last].l;
                            goto end;
                        }
                    }
                    if(ver[r][1].find(u)!=ver[r][1].end()){
                        last=ver[r][1][u];
                        if(x[last].d==d){
                            r=x[last].r;
                            goto end;
                        }
                    }
                    if(hor[u][0].find(l)!=hor[u][0].end()){
                        int last=hor[u][0][l];
                        if(x[last].r==r){
                            u=x[last].u;
                            goto end;
                        }
                    }
                    if(hor[d][1].find(l)!=hor[d][1].end()){
                        int last=hor[d][1][l];
                        if(x[last].r==r){
                            d=x[last].d;
                            goto end;
                        }
                    }
                    break;
                    end:erase(last),ans++;
                }
                x[++tt]={u,d,l,r};
                hor[u][1][l]=hor[d][0][l]=tt;
                ver[l][1][u]=ver[r][0][u]=tt;
            }
    if(ans==tt-1)puts("YES");
    else puts("NO");
    return 0;
}
/*
3 4
0000
0111
101
101
110
*/ 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7984kb

input:

3 4
0000
0111
101
101
110

output:

YES

result:

ok answer is YES

Test #2:

score: 0
Accepted
time: 1ms
memory: 8228kb

input:

3 3
110
011
01
11
10

output:

NO

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 67ms
memory: 153660kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #4:

score: 0
Accepted
time: 278ms
memory: 46164kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #5:

score: 0
Accepted
time: 44ms
memory: 10960kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #6:

score: 0
Accepted
time: 20ms
memory: 12408kb

input:

1500 1500
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

YES

result:

ok answer is YES

Test #7:

score: 0
Accepted
time: 275ms
memory: 46004kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #8:

score: 0
Accepted
time: 555ms
memory: 99328kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #9:

score: 0
Accepted
time: 555ms
memory: 99200kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #10:

score: 0
Accepted
time: 556ms
memory: 99188kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #11:

score: 0
Accepted
time: 546ms
memory: 98988kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #12:

score: 0
Accepted
time: 406ms
memory: 72776kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

YES

result:

ok answer is YES

Test #13:

score: 0
Accepted
time: 757ms
memory: 70332kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

ok answer is NO

Test #14:

score: -100
Wrong Answer
time: 440ms
memory: 60084kb

input:

1500 1500
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

NO

result:

wrong answer expected YES, found NO