QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760963 | #9560. Judgement | Coffins | WA | 2ms | 11344kb | C++14 | 3.4kb | 2024-11-18 20:23:48 | 2024-11-18 20:23:49 |
Judging History
answer
#include<bits/stdc++.h>
#define NO_MANA return \
cout<<"NO\n",void();
using namespace std;
const int N=505;
int n,m,V,a[N][N],id[N][N];
char s[N];int rx,ry,bx,by;
vector<int> edge[N*N];
int tg[N],col[N],dg[N],tot;
int mx[4]={1,-1,0,0};
int my[4]={0,0,1,-1};
vector<int> vc[N];
bool vs[N];int c[N];
int b[N];queue<int> q;
void lk(int x,int y)
{edge[x].push_back(y);}
void solve()
{
cin>>n>>m;V=0;
cin>>rx>>ry>>bx>>by;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=id[i][j]=0;
for(int i=1;i<=n;i++)
{
cin>>s+1;
for(int j=1;j<=m;j++)
if(s[j]=='B')a[i][j]=1;
else if(s[j]=='R')a[i][j]=2;
}for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!a[i][j])continue;
if(i==rx&&j==ry)continue;
if(i==bx&&j==by)continue;
id[i][j]=++V;c[V]=a[i][j];
}for(int i=1;i<=V;i++)edge[i].clear();
for(int i=1;i<=V;i++)tg[i]=0;
for(int x=1;x<=n;x++)
for(int y=1;y<=m;y++)
{
if(!id[x][y])continue;
for(int t=0;t<=3;t++)
{
int nx=x+mx[t];
int ny=y+my[t];
if(id[nx][ny])
lk(id[x][y],id[nx][ny]);
}
}vector<int> vec[3];
for(int t=0;t<=3;t++)
{
int nx=rx+mx[t];
int ny=ry+my[t];
if(id[nx][ny])vec[1].
push_back(id[nx][ny]);
nx=bx+mx[t];
ny=by+my[t];
if(id[nx][ny])vec[2].
push_back(id[nx][ny]);
}for(int u:vec[1])tg[u]|=1;
for(int u:vec[2])tg[u]|=2;
for(int i=1;i<=V;i++)
dg[i]=edge[i].size(),vs[i]=0;
for(int s=1;s<=V;s++)
{
if(vs[s])continue;
q.push(s);vs[s]=1;
tot++;col[tot]=1;
vc[tot].clear();
while(!q.empty())
{
int u=q.front();q.pop();
vc[tot].push_back(u);
col[tot]|=tg[u];
for(auto v:edge[u])
{
if(vs[v])continue;
vs[v]=1,q.push(v);
}
}
//cout<<tot<<' '<<col[tot]<<'\n';
//for(int u:vc[tot])cout<<u<<' ';
//cout<<'\n';
}
for(int t=1;t<=tot;t++)
if(!col[t])NO_MANA;
for(int t=1;t<=tot;t++)
if(col[t]^3)
{
bool fl=1;
for(int u:vc[t])
fl&=(c[u]==col[t]);
if(!fl)NO_MANA
}
else
{
bool fl=0;
for(int u:vc[t])
for(auto v:edge[u])
fl|=(c[u]==c[v]);
for(int u:vc[t])
fl|=(c[u]&tg[u]);
if(!fl)NO_MANA;
if(vc[t].size()==1)
continue;fl=0;
for(int u:vc[t])
fl|=(dg[u]>=3);
if(fl)continue;
for(int u:vc[t])
fl|=(dg[u]==1);
if(!fl)continue;fl=0;
for(int u:vc[t])
fl|=(dg[u]>1&&tg[u]);
if(fl)continue;fl=0;
for(int u:vc[t])
fl|=(tg[u]==3);
if(fl)continue;fl=0;
for(int u:vc[t])
if(tg[u]==1)b[m=1]=u;
while(1)
{
int u=b[m];bool fl=0;
for(auto v:edge[u])
{
if(m>1&&v^b[m-1])
b[++m]=v,fl=1;
}if(!fl)break;
}int l=0,r=m+1;
while(l<m&&c[b[l+1]]==1)l++;
while(r>1&&c[b[r-1]]==2)r--;
if(l+1!=r)NO_MANA;
}cout<<"YES\n";
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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: 10164kb
input:
4 3 3 1 1 1 2 RBB RRR BBR 6 6 1 1 6 6 RRRRRR BBBBBR BRRRBR BRBBBR BRRRRR BBBBBB 5 5 3 3 4 4 BBR.B BBR.B RRR.B ...BB BBBB. 1 5 1 1 1 3 RBBBR
output:
YES YES NO NO
result:
ok 4 token(s): yes count is 2, no count is 2
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 11344kb
input:
18 4 4 3 3 2 2 .... .BB. .BR. .... 7 8 5 6 3 3 ..RRRRRR ..R....R BBBBBB.R B.B..R.R B.RRRRRR B....B.. BBBBBB.. 5 2 3 1 3 2 B. BR RB BR .R 3 3 2 2 1 2 .BB BRB BBB 3 3 1 2 3 2 RRR ... BBB 3 3 1 1 1 3 RRB ... BRR 3 3 1 1 3 1 RRB ... BRR 3 3 3 1 1 1 BBR ..R RBB 3 3 2 2 2 1 .BB BRB .RB 1 2 1 1 1 2 RB 2 2 ...
output:
YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO
result:
wrong answer expected YES, found NO [5th token]