Submission #1040487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040487		isaachew	Toy (CEOI24_toy)	C++17	100 / 100	258 ms	207140 KiB

Main

#include <bits/stdc++.h>
/*
 */
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int w,h,k,l;
    std::cin>>w>>h>>k>>l;
    std::vector<std::string> board;
    int x,y,z;
    int dx,dy;
    std::cin>>z>>y>>x>>z;//z does nothing
    std::vector<std::vector<int>> edges(w*h);
    for(int i=0;i<h;i++){
        std::string s;
        std::cin>>s;
        board.push_back(s);
    }
    std::vector<std::vector<int>> ledges(h,std::vector<int>(w));
    std::vector<std::vector<int>> redges(h,std::vector<int>(w));
    std::vector<std::vector<int>> uedges(h,std::vector<int>(w));
    std::vector<std::vector<int>> dedges(h,std::vector<int>(w));
    
    std::vector<int> visited(w*h);
    for(int i=0;i<h;i++){
        int mre=0;
        for(int j=0;j<w;j++){
            if(board[i][j]=='*'){
                dy=i,dx=j;
            }
            if(board[i][j]=='X'){
                for(;mre<j;mre++){
                    redges[i][mre]=j;
                }
                mre=j+1;
            }
            ledges[i][j]=mre;
        }
        for(;mre<w;mre++){
            redges[i][mre]=w;
        }
    }
    for(int i=0;i<w;i++){
        int mre=0;
        for(int j=0;j<h;j++){
            if(board[j][i]=='X'){
                for(;mre<j;mre++){
                    dedges[mre][i]=j;
                }
                mre=j+1;
            }
            uedges[j][i]=mre;
        }
        for(;mre<h;mre++){
            dedges[mre][i]=h;
        }
    }
    
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(i+1<h){//down/up
                int leftx=std::max(ledges[i][j],ledges[i+1][j]);
                int rightx=std::min(redges[i][j],redges[i+1][j]);
                if(leftx+k<=rightx){
                    edges[i*w+j].push_back((i+1)*w+j);
                    edges[(i+1)*w+j].push_back(i*w+j);
                }
            }
            if(j+1<w){
                int upy=std::max(uedges[i][j],uedges[i][j+1]);
                int downy=std::min(dedges[i][j],dedges[i][j+1]);
                if(upy+l<=downy){
                    edges[i*w+j].push_back(i*w+(j+1));
                    edges[i*w+(j+1)].push_back(i*w+j);
                }
            }
        }
    }
    std::vector<int> tovisit;
    tovisit.push_back(y*w+x);
    while(!tovisit.empty()){
        int cur=tovisit.back();
        tovisit.pop_back();
        if(visited[cur])continue;
        visited[cur]=1;
        for(int i:edges[cur]){
            tovisit.push_back(i);
        }
    }
    std::cout<<(visited[dy*w+dx]?"YES\n":"NO\n");
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:90:29: warning: 'dx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     std::cout<<(visited[dy*w+dx]?"YES\n":"NO\n");
      |                         ~~~~^~~
Main.cpp:90:27: warning: 'dy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |     std::cout<<(visited[dy*w+dx]?"YES\n":"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