QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864571 | #4773. Piece it together | rladbeka | RE | 0ms | 3712kb | C++20 | 5.5kb | 2025-01-20 19:17:50 | 2025-01-20 19:17:52 |
Judging History
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...