QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425546 | #4773. Piece it together | Ge_QingHui | TL | 2ms | 6156kb | C++14 | 2.0kb | 2024-05-30 13:27:15 | 2024-05-30 13:27:15 |
Judging History
answer
#pragma GCC optmize(2,3,"Ofast","inline","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+9;
int n,m,cnt,mat[N],id[2][509][509];
bool vst[N];
char mp[509][509];
int hd[N],tot,to[N<<2],nxt[N<<2];
bool dfs(int x){
vst[x]=1;
for(int i=hd[x];i;i=nxt[i]){
int u=to[i],v=mat[u];
if(v<0 || !vst[v] && dfs(v)){
mat[x]=u; mat[u]=x;
return true;
}
}
return false;
}
int calc(){
int res=0;
memset(mat,-1,sizeof(mat));
for(int i=1;i<=cnt;i++){
if(mat[i]<0){
memset(vst,0,sizeof(vst));
if(dfs(i)) res++;
}
}
return res;
}
inline void add(int x,int y){
tot++; nxt[tot]=hd[x]; to[tot]=y; hd[x]=tot;
tot++; nxt[tot]=hd[y]; to[tot]=x; hd[y]=tot;
}
const int dx[5]={0,0,1,-1};
const int dy[5]={1,-1,0,0};
void solve(){
cnt=0; cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>mp[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]=='.') continue;
if(mp[i][j]=='W') id[0][i][j]=++cnt;
if(mp[i][j]=='B') id[0][i][j]=++cnt,id[1][i][j]=++cnt;
}
for(int i=1;i<=cnt;i++) hd[i]=0;
tot=0;
int sB=0,sW=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(mp[i][j]=='B'){
for(int k=0;k<4;k++){
int ni=i+dx[k],nj=j+dy[k];
if(1<=ni && ni<=n && 1<=nj && nj<=m && mp[ni][nj]=='W'){
add(id[(k<2)][i][j],id[0][ni][nj]);
}
}
sB++;
}
else if(mp[i][j]=='W') sW++;
}
if(sB*2!=sW) puts("NO");
else if(calc()!=sW) puts("NO");
else puts("YES");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int T; cin>>T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 6156kb
input:
2 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW
output:
YES NO
result:
ok 2 token(s): yes count is 1, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
70 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW 1 1 B 3 3 ... .W. ... 2 2 W. BW 2 3 .W. WBW 1 3 WBW 2 5 .W.W. WB.BW 2 2 WW .B 2 2 WB .. 3 3 WWB BWW WWB 3 5 .W.WB WBW.W ...WB 4 5 ..W.. .WBW. WBWBW .WBW. 3 9 BWW...W.. WWBW..BW. ..WB..WBW 4 12 BWWBWWBWWBWW WWBWWBWWBWWB BWWBWWBWWBWW WWBWWBWWBWWB 7 7 BWWBBWW WBWWW...