Submission #1193461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193461		Unforgettablepl	Toy (CEOI24_toy)	C++20	100 / 100	307 ms	459032 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int W,H,K,L;
    cin >> W >> H >> K >> L;
    int xSt,ySt;
    {
        int t;
        cin >> t >> xSt >> ySt >> t;
        xSt++;
        ySt++;
    }
    vector visited(H+2,vector<bool>(W+2));
    for(int i=0;i<=H+1;i++)visited[i][0]=visited[i][W+1]=true;
    for(int i=0;i<=W+1;i++)visited[0][i]=visited[H+1][i]=true;
    int xEd,yEd;
    
    vector<vector<int>> verticals(W+1);
    for(int i=1;i<=W;i++)verticals[i].emplace_back(0);
    for(int i=1;i<=W;i++)verticals[i].emplace_back(H+1);
    
    vector<vector<int>> horizontals(H+1);
    for(int i=1;i<=H;i++)horizontals[i].emplace_back(0);
    for(int i=1;i<=H;i++)horizontals[i].emplace_back(W+1);
    
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            char x;cin>>x;
            if(x=='X'){
                visited[i][j]=true;
                verticals[j].emplace_back(i);
                horizontals[i].emplace_back(j);
            }
            if(x=='*'){
                xEd = i;
                yEd = j;
            }
        }
    }

    for(int i=1;i<=W;i++)sort(verticals[i].begin(),verticals[i].end());
    for(int i=1;i<=H;i++)sort(horizontals[i].begin(),horizontals[i].end());

    auto getVerticalRange = [&](int y,int x){
        auto iter = lower_bound(verticals[x].begin(),verticals[x].end(),y);
        assert(iter!=verticals[x].end());
        assert(iter!=verticals[x].begin()); 
        auto bef = iter-1;
        return make_pair(*bef,*iter);
    };

    auto getHorizonalRange = [&](int x,int y){
        auto iter = lower_bound(horizontals[x].begin(),horizontals[x].end(),y);
        assert(iter!=horizontals[x].end());
        assert(iter!=horizontals[x].begin());
        auto bef = iter-1;
        return make_pair(*bef,*iter);
    };

    function<void(int,int)> dfs = [&](int x,int y){
        visited[x][y]=true;
        auto myHori = getHorizonalRange(x,y);
        auto myVeri = getVerticalRange(x,y);
        if(!visited[x-1][y]){
            auto t = getHorizonalRange(x-1,y);
            t.first=max(t.first,myHori.first);
            t.second=min(t.second,myHori.second);
            int r = t.second-t.first-1;
            if(r>=K)dfs(x-1,y);
        }
        if(!visited[x+1][y]){
            auto t = getHorizonalRange(x+1,y);
            t.first=max(t.first,myHori.first);
            t.second=min(t.second,myHori.second);
            int r = t.second-t.first-1;
            if(r>=K)dfs(x+1,y);
        }
        if(!visited[x][y-1]){
            auto t = getVerticalRange(x,y-1);
            t.first=max(t.first,myVeri.first);
            t.second=min(t.second,myVeri.second);
            int r = t.second-t.first-1;
            if(r>=L)dfs(x,y-1);
        }
        if(!visited[x][y+1]){
            auto t = getVerticalRange(x,y+1);
            t.first=max(t.first,myVeri.first);
            t.second=min(t.second,myVeri.second);
            int r = t.second-t.first-1;
            if(r>=L)dfs(x,y+1);
        }
    };

    dfs(xSt,ySt);
    if(visited[xEd][yEd]){
        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