Submission #1342761

#TimeUsernameProblemLanguageResultExecution timeMemory
1342761fatime_aslan_156Toy (CEOI24_toy)C++20
0 / 100
5 ms1092 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll>e;
vector<vector<ll>>c,f;
vector<vector<bool>>ce;
map<pair<ll,ll>,bool>m;
ll w,h,k,l;
bool be=0;
vector<ll>dx={1,0,-1,0};
vector<ll>dy={0,1,0,-1};
void bfs(ll a,ll b)
{
    //cout<<4<<endl;
    queue<pair<ll,ll>>q;
    q.push({a,b});
    ce[a][b]=1;
    //cout<<8<<endl;
    while(!q.empty())
    {
        //cout<<5<<endl;
        auto [u,ke]=q.front();
        q.pop();
        if(u==e.first && ke==e.second)
        {
            be=1;
            return;
        }
        for(int i=0;i<4;i++)
        {
            ll r=u+dx[i],o=dy[i]+ke;
            if(r<=h && o<=w && r>=0 && o>=0 && !ce[r][o] && !binary_search(c[r].begin(),c[r].end(),o) && !binary_search(f[o].begin(),f[o].end(),r))
            {
                auto xs=upper_bound(c[r].begin(),c[r].end(),o);
                ll p,n;
                if(xs==c[r].end())
                {
                    n=w+1;
                }
                else
                n=*xs;
                if(xs==c[r].begin())
                {
                    p=-1;
                }
                else
                p=*(--xs);
                //cout<<r<<' '<<o<<' '<<n<<' '<<p<<endl;
                if(n-p<=k)
                continue;
                auto xy=upper_bound(f[o].begin(),f[o].end(),r);
                ll pu,nu;
                if(xy==f[o].end())
                {
                    nu=h+1;
                }
                else
                nu=*xy;
                if(xy==f[o].begin())
                {
                    pu=-1;
                }
                else
                pu=*(--xy);
                if(nu-pu<=l)
                continue;
                q.push({r,o});
                ce[r][o]=1;
            }
        }
    }
}
int main()
{
    cin>>w>>h>>k>>l;
    //cout<<h<<endl;
    //cout<<k<<endl;
    w--;
    h--;
    ll z,x,g,rew;
    cin>>z>>x>>g>>rew;
    ce.assign(h+2,vector<bool>(w+2));
    c.assign(h+1,{});
    f.assign(w+1,{});
    for(int i=0;i<=h;i++)
    {
        string s;
        cin>>s;
        //cout<<s<<endl;
        for(int j=0;j<=w;j++)
        {
            if(s[j]=='*')
            {
                e={i,j};
            }
            else if(s[j]=='X')
            {
                c[i].push_back(j);
                f[j].push_back(i);
            }
            //cout<<s[j];
        }
        //cout<<endl;
    }
    //cout<<c[0][0]<<endl;
    for(int i=0;i<c.size();i++)
    {
        if(c[i].empty())
        continue;
        sort(c[i].begin(),c[i].end());
    }
    for(int i=0;i<f.size();i++)
    {
        if(f[i].empty())
        continue;
        sort(f[i].begin(),f[i].end());
        //for(int j=0;j<f[i].size();j++)
        //cout<<i<<' '<<f[i][j]<<endl;
    }
    bfs(x,g);
    if(be)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...