QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864571#4773. Piece it togetherrladbekaRE 0ms3712kbC++205.5kb2025-01-20 19:17:502025-01-20 19:17:52

Judging History

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

  • [2025-01-20 19:17:52]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3712kb
  • [2025-01-20 19:17:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef array<ll, 2> pii;
typedef array<ll, 3> tii;
typedef vector<pii> vpii;
typedef double lf;
typedef string S;
#define V vector
#define PQ priority_queue
#define fastio; cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define vcin; for(int i=0; i<n; i++) cin >> v[i];
#define forf(i, s, e) for(ll i=s; i<e; i++)
#define forb(i, s, e) for(ll i=s-1; i>=e; i--)
#define pb push_back
#define sortv(v) sort(v.begin(), v.end())
#define sortc(v, cmp) sort(v.begin(), v.end(), cmp)
#define all(v) v.begin(), v.end()
const ll mod=1e9+7, MOD=998244353;
const ll dir4[4][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
const ll dir8[8][2]={{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
const ll inf=2147483647, linf=9223372036854775807;
const double pi=acos(-1), E=2.718281828459;
ll gcd(ll a, ll b){return b?gcd(b, a%b):a;}

ll n, e, N, M, Wc, Bc;
vvi edge, redge;
V<bool> vsd, rvsd;
vi vseq;
vvi scc;

void dfs(ll pnt){
    vsd[pnt]=true;
    for(ll i : edge[pnt]){
        if(!vsd[i]) dfs(i);
    }
    vseq.pb(pnt);
}

void rdfs(ll pnt){
    rvsd[pnt]=true;
    for(ll i : redge[pnt]){
        if(!rvsd[i]) rdfs(i);
    }
    scc[scc.size()-1].pb(pnt);
}

bool _2sat(){
    vi sat(n);

    forf(cnt, 0, scc.size())
        for(ll i : scc[cnt])
            sat[i]=cnt+1;

    forf(i, 0, 2*N*M) if(sat[i]==sat[i+2*N*M]) return false;

    forf(i, 0, N){
        forf(j, 0, M-1){
            ll L=i*M*j, O=i*M+(j+1);
            if(sat[L]==sat[O]) return false;
        }
    }
    forf(i, 0, N-1){
        forf(j, 0, M){
            ll D=i*M*j, O=(i+1)*M+j;
            if(sat[D]==sat[O]) return false;
        }
    }
    return true;
}

bool solve(){
    cin >> N >> M; n=N*M*4; // 0,1 UD / 2,3 LR
    edge.clear(); redge.clear(); vsd.clear(); rvsd.clear();
    vseq.clear(); scc.clear();
    edge.resize(n); redge.resize(n);
    vsd.resize(n); rvsd.resize(n);
    Bc=0; Wc=0;

    V<string> s(N);
    forf(i, 0, N) cin >> s[i];
    forf(i, 0, N){
        forf(j, 0, M){
            Wc+=(s[i][j]=='W');
            Bc+=(s[i][j]=='B');

            if(s[i][j]=='B'){
                bool up=(i>0 && s[i-1][j]=='W');
                bool down=(i<N-1 && s[i+1][j]=='W');
                ll O=M*i+j, U=M*(i-1)+j, L=M*i+(j-1), lr=N*M, Not=2*N*M;
                if(up && down){
                    edge[U+Not].pb(O);
                    edge[O+Not].pb(U);
                }
                else if(up){
                    edge[U+Not].pb(U);
                }
                else if(down){
                    edge[O+Not].pb(O);
                }
                else{
                    return false;
                }

                bool left=(j>0 && s[i][j-1]=='W');
                bool right=(j<M-1 && s[i][j+1]=='W');


                if(left && right){
                    edge[L+Not+lr].pb(O+lr);
                    edge[O+Not+lr].pb(L+lr);
                }
                else if(left){
                    edge[L+Not+lr].pb(L+lr);
                }
                else if(right){
                    edge[O+Not+lr].pb(O+lr);
                }
                else{
                    return false;
                }

            }
        }
    }

    forf(i, 0, N){
        forf(j, 0, M){
            if(s[i][j]!='W') continue;

            if(i<N-1 && j<M-1 && s[i+1][j]=='B' && s[i][j+1]=='B'){
                ll UD=i*M+j, LR=i*M+j+N*M, Not=2*N*M;
                edge[UD].pb(LR+Not);
                edge[LR].pb(UD+Not);
                edge[UD+Not].pb(LR);
                edge[LR+Not].pb(UD);
            }
            if(i<N-1 && j>0 && s[i+1][j]=='B' && s[i][j-1]=='B'){
                ll UD=i*M+j, LR=i*M+(j-1)+N*M, Not=2*N*M;
                edge[UD].pb(LR+Not);
                edge[LR].pb(UD+Not);
                edge[UD+Not].pb(LR);
                edge[LR+Not].pb(UD);
            }
            if(i>0 && j<M-1 && s[i-1][j]=='B' && s[i][j+1]=='B'){
                ll UD=(i-1)*M+j, LR=i*M+j+N*M, Not=2*N*M;
                edge[UD].pb(LR+Not);
                edge[LR].pb(UD+Not);
                edge[UD+Not].pb(LR);
                edge[LR+Not].pb(UD);
            }
            if(i>0 && j>0 && s[i-1][j]=='B' && s[i][j-1]=='B'){
                ll UD=(i-1)*M+j, LR=i*M+(j-1)+N*M, Not=2*N*M;
                edge[UD].pb(LR+Not);
                edge[LR].pb(UD+Not);
                edge[UD+Not].pb(LR);
                edge[LR+Not].pb(UD);
            }
        }
    }

    if(Wc!=Bc*2) return false;

    forf(i, 0, n)
        for(ll j : edge[i])
            redge[j].pb(i);

    /*forf(i, 0, n){
        cout << i << ") ";
        for(ll j : edge[i])
            cout << j << " ";
        cout << "\n";
    }*/

    forf(i, 0, n){
        sortv(edge[i]);
        sortv(redge[i]);
    }

    forf(i, 0, n){
        if(!vsd[i]) dfs(i);
    }

    while(vseq.size()){
        ll vt=vseq[vseq.size()-1];
        if(rvsd[vt]){
            vseq.pop_back();
            continue;
        }

        scc.pb({});
        rdfs(vt);
        sortv(scc[scc.size()-1]);
    }

    /*cout << " \n";
    for(vi v : scc){
        for(ll i : v) cout << i <<" ";
        cout <<" / ";
    }
    cout << "\n";*/

    return _2sat();


}

int main(){
    fastio;

    ll t; cin >> t;
    while(t--){
        cout << (solve()?"YES\n":"NO\n");
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

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
Runtime Error

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: