Submission #1118406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118406		Tenis0206	Toy (CEOI24_toy)	C++11	100 / 100	76 ms	42728 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1500;

int n,m;
int lv,lh,xv,yv,xh,yh;
char a[nmax + 5][nmax + 5];

bool sel[nmax + 5][nmax + 5];

int st[nmax + 5][nmax + 5], dr[nmax + 5][nmax + 5], sus[nmax + 5][nmax + 5], jos[nmax + 5][nmax + 5];

void precalc()
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(a[i][j] == 'X')
            {
                sus[i][j] = i + 1;
            }
            else
            {
                if(i == 0)
                {
                    sus[i][j] = 0;
                }
                else
                {
                    sus[i][j] = sus[i - 1][j];
                }
            }

            if(a[i][j] == 'X')
            {
                st[i][j] = j + 1;
            }
            else
            {
                if(j == 0)
                {
                    st[i][j] = 0;
                }
                else
                {
                    st[i][j] = st[i][j - 1];
                }
            }
        }
    }

    for(int i=n-1;i>=0;i--)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(a[i][j] == 'X')
            {
                jos[i][j] = i - 1;
            }
            else
            {
                if(i == n - 1)
                {
                    jos[i][j] = n - 1;
                }
                else
                {
                    jos[i][j] = jos[i + 1][j];
                }
            }

            if(a[i][j] == 'X')
            {
                dr[i][j] = j - 1;
            }
            else
            {
                if(j == m - 1)
                {
                    dr[i][j] = m - 1;
                }
                else
                {
                    dr[i][j] = dr[i][j + 1];
                }
            }
        }
    }
}

int intersect(int a, int b, int c, int d)
{
    if(a > c)
    {
        swap(a, c);
        swap(b, d);
    }
    if(c > b)
    {
        return 0;
    }
    if(d <= b)
    {
        return (d - c + 1);
    }
    return (b - c + 1);
}

void bfs(int x, int y)
{
    queue<pair<int,int>> q;
    q.push({x, y});
    sel[x][y] = true;
    while(!q.empty())
    {
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
        /// catre sus
        if(i != 0 && !sel[i - 1][j] && a[i - 1][j] != 'X' && intersect(st[i][j], dr[i][j], st[i - 1][j], dr[i - 1][j]) >= lh)
        {
            sel[i - 1][j] = true;
            q.push({i - 1, j});
        }

        /// catre jos
        if(i < n - 1 && !sel[i + 1][j] && a[i + 1][j] != 'X' && intersect(st[i][j], dr[i][j], st[i + 1][j], dr[i + 1][j]) >= lh)
        {
            sel[i + 1][j] = true;
            q.push({i + 1, j});
        }

        /// catre stanga
        if(j != 0 && !sel[i][j - 1] && a[i][j - 1] != 'X' && intersect(sus[i][j], jos[i][j], sus[i][j - 1], jos[i][j - 1]) >= lv)
        {
            sel[i][j - 1] = true;
            q.push({i, j - 1});
        }

        /// catre dreapta
        if(j < m - 1 && !sel[i][j + 1] && a[i][j + 1] != 'X' && intersect(sus[i][j], jos[i][j], sus[i][j + 1], jos[i][j + 1]) >= lv)
        {
            sel[i][j + 1] = true;
            q.push({i, j + 1});
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>m>>n>>lh>>lv;
    cin>>yh>>xh>>yv>>xv;
    int xs = xh;
    int ys = yv;
    int xf = 0, yf = 0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>a[i][j];
            if(a[i][j] == '*')
            {
                xf = i;
                yf = j;
            }
        }
    }
    precalc();
    bfs(xs, ys);
    if(sel[xf][yf])
    {
        cout<<"YES\n";
    }
    else
    {
        cout<<"NO\n";
    }
    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