Submission #1231880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231880		PVM_pvm	Toy (CEOI24_toy)	C++20	100 / 100	290 ms	216344 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1507
int ww,h,k,l;
int xh,yh,xv,yv;
int xg,yg;
int xs,ys;
bool bl[MAXN][MAXN];
int lf[MAXN][MAXN],rt[MAXN][MAXN];
int up[MAXN][MAXN],dw[MAXN][MAXN];
bool b[MAXN][MAXN];
pair<int,int> dl[4]={ {1,0} , {-1,0} , {0,-1} , {0,1} };
void dfs(int x, int y)
{
    b[x][y]=1;
    for (int dd=0;dd<4;dd++)
    {
        int nx=x+dl[dd].first;
        int ny=y+dl[dd].second;
        if (nx<0 || nx>=h) continue;
        if (ny<0 || ny>=ww) continue;
        if (bl[nx][ny]) continue;
        if (b[nx][ny]) continue;
        int dlred=rt[nx][ny]-lf[nx][ny]+1;
        if (dlred<k) continue;
        int dlkol=dw[nx][ny]-up[nx][ny]+1;
        if (dlkol<l) continue;
        int ort=min(rt[nx][ny],rt[x][y]);
        int olf=max(lf[nx][ny],lf[x][y]);
        int oup=max(up[nx][ny],up[x][y]);
        int odw=min(dw[nx][ny],dw[x][y]);
        int odlkol=odw-oup+1;
        int odlred=ort-olf+1;
        if (odlred<k) continue;
        if (odlkol<l) continue;
        dfs(nx,ny);
    }
}
int main()
{
    cin>>ww>>h>>k>>l;
    cin>>xh>>yh>>xv>>yv;
    for (int q=0;q<h;q++)
    {
        string s;
        cin>>s;
        for (int w=0;w<ww;w++)
        {
            if (s[w]=='X') bl[q][w]=1;
            else
            {
                bl[q][w]=0;
                if (s[w]=='*')
                {
                    xg=w;
                    yg=q;
                }
            }
        }
    }
    xs=xv;
    ys=yh;
    for (int q=0;q<h;q++)
    {
        if (bl[q][0]) lf[q][0]=0;
        else lf[q][0]=-1;
        for (int w=1;w<ww;w++)
        {
            if (bl[q][w]) lf[q][w]=w;
            else lf[q][w]=lf[q][w-1];
        }
        if (bl[q][ww-1]) rt[q][ww-1]=ww-1;
        else rt[q][ww-1]=ww;
        for (int w=ww-2;w>=0;w--)
        {
            if (bl[q][w]) rt[q][w]=w;
            else rt[q][w]=rt[q][w+1];
        }
    }
    for (int w=0;w<ww;w++)
    {
        if (bl[0][w]) up[0][w]=0;
        else up[0][w]=-1;
        for (int q=1;q<h;q++)
        {
            if (bl[q][w]) up[q][w]=q;
            else up[q][w]=up[q-1][w];
        }
        if (bl[h-1][w]) dw[h-1][w]=h-1;
        else dw[h-1][w]=h;
        for (int q=h-2;q>=0;q--)
        {
            if (bl[q][w]) dw[q][w]=q;
            else dw[q][w]=dw[q+1][w];
        }
    }
    for (int q=0;q<h;q++)
    {
        for (int w=0;w<ww;w++)
        {
            lf[q][w]++;
            rt[q][w]--;
            up[q][w]++;
            dw[q][w]--;
        }
    }
    dfs(ys,xs);
    if (b[yg][xg])
    {
        cout<<"YES\n";
    }
    else cout<<"NO\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27