QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760983#9560. JudgementCoffinsWA 3ms10944kbC++143.4kb2024-11-18 20:29:552024-11-18 20:29:55

Judging History

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

  • [2024-11-18 20:29:55]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:10944kb
  • [2024-11-18 20:29:55]
  • 提交

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]=='R')a[i][j]=1;
        else if(s[j]=='B')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]=0;
        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);
            }
        }
        //<<tot<<' '<<col[tot]<<'\n';
        //for(int u:vc[tot])cout<<u<<' '<<c[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])>0);
        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: 3ms
memory: 10064kb

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: 3ms
memory: 10944kb

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
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO

result:

wrong answer expected YES, found NO [10th token]