QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425546#4773. Piece it togetherGe_QingHuiTL 2ms6156kbC++142.0kb2024-05-30 13:27:152024-05-30 13:27:15

Judging History

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

  • [2024-05-30 13:27:15]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:6156kb
  • [2024-05-30 13:27:15]
  • 提交

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...

output:


result: