Submission #1090371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090371		lucri	Toy (CEOI24_toy)	C++17	100 / 100	115 ms	42732 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n,m,l,c,x,y,xx,yy,stop[4][1510][1510];
char a[1510][1510];
bool ok[1510][1510];
queue<pair<int,int>>q;
bool verificaorizontal(int i,int ii,int j)
{
    return (min(stop[1][i][j],stop[1][ii][j])-max(stop[0][i][j],stop[0][ii][j])-1)>=c;
}
bool verificavertical(int j,int jj,int i)
{
    return (min(stop[3][i][j],stop[3][i][jj])-max(stop[2][i][j],stop[2][i][jj])-1)>=l;
}
int main()
{
    cin>>m>>n>>c>>l>>x>>y>>xx>>yy;
    ok[y][xx]=true;
    q.push({y,xx});
    for(int i=0;i<n;++i)
        cin>>a[i];
    for(int i=0;i<n;++i)
    {
        if(a[i][0]!='X')
            stop[0][i][0]=-1;
        else
            stop[0][i][0]=0;
        for(int j=1;j<m;++j)
            if(a[i][j]!='X')
                stop[0][i][j]=stop[0][i][j-1];
            else
                stop[0][i][j]=j;
        if(a[i][m-1]!='X')
            stop[1][i][m-1]=m;
        else
            stop[1][i][m-1]=m-1;
        for(int j=m-2;j>=0;--j)
            if(a[i][j]!='X')
                stop[1][i][j]=stop[1][i][j+1];
            else
                stop[1][i][j]=j;
    }
    for(int j=0;j<m;++j)
    {
        if(a[0][j]!='X')
            stop[2][0][j]=-1;
        else
            stop[2][0][j]=0;
        for(int i=1;i<n;++i)
            if(a[i][j]!='X')
                stop[2][i][j]=stop[2][i-1][j];
            else
                stop[2][i][j]=i;
        if(a[n-1][j]!='X')
            stop[3][n-1][j]=n;
        else
            stop[3][n-1][j]=n-1;
        for(int i=n-2;i>=0;--i)
            if(a[i][j]!='X')
                stop[3][i][j]=stop[3][i+1][j];
            else
                stop[3][i][j]=i;
    }
    while(!q.empty())
    {
        int i=q.front().first;
        int j=q.front().second;
        q.pop();
        if(i&&ok[i-1][j]==false)
        {
            if(a[i-1][j]!='X'&&verificaorizontal(i,i-1,j))
            {
                ok[i-1][j]=true;
                q.push({i-1,j});
            }
        }
        if(i<n-1&&ok[i+1][j]==false)
        {
            if(a[i+1][j]!='X'&&verificaorizontal(i,i+1,j))
            {
                ok[i+1][j]=true;
                q.push({i+1,j});
            }
        }
        if(j&&ok[i][j-1]==false)
        {
            if(a[i][j-1]!='X'&&verificavertical(j,j-1,i))
            {
                ok[i][j-1]=true;
                q.push({i,j-1});
            }
        }
        if(j<m-1&&ok[i][j+1]==false)
        {
            if(a[i][j+1]!='X'&&verificavertical(j,j+1,i))
            {
                ok[i][j+1]=true;
                q.push({i,j+1});
            }
        }
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<m;++j)
            if(a[i][j]=='*')
            {
                if(ok[i][j]==true)
                    cout<<"YES";
                else
                    cout<<"NO";
            }
    return 0;
}

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