QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#395729 | #6746. Merge the Rectangles | Gaomer | WA | 757ms | 153660kb | C++14 | 2.8kb | 2024-04-21 17:50:00 | 2024-04-21 17:50:00 |
Judging History
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