Submission #1221003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221003		KindaGoodGames	Toy (CEOI24_toy)	C++20	35 / 100	1608 ms	741288 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define tiiii tuple<int,int,int,int>

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int W, H, w, h;
    cin >> W >> H >> w >> h;

    int XH, YH, XV, YV;
    cin >>XH >> YH >> XV >> YV;

    vector<vector<char>> grid(H, vector<char>(W));

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> grid[i][j];
        }
    }

    vector<vector<bool>> validH(H, vector<bool>(W));
    vector<vector<bool>> validV(H, vector<bool>(W));
    for(int i = 0; i < H; i++){
        for(int j = 0; j <= W-w; j++){
            bool valid = true;
            for(int k = j; k < j+w; k++){
                if(grid[i][k] == 'X'){
                    valid = false;
                    break;
                }
            }
            validH[i][j] = valid;
        }
    }
    for(int i = 0; i <= H-h; i++){
        for(int j = 0; j < W; j++){
            bool valid = true;
            for(int k = i; k < i+h; k++){
                if(grid[k][j] == 'X'){
                    valid = false;
                    break;
                }
            }
            validV[i][j] = valid;
        }
    }


    vector<vector<vector<vector<bool>>>> vis(W, vector<vector<vector<bool>>>(H, vector<vector<bool>>(W, vector<bool>(H)))); 

    stack<tiiii> q;
    q.push({XH, YH, XV, YV});

    bool res = false;

    while(q.size()){
        if(res) break;
        int xh, yh, xv, yv;
        tie(xh, yh, xv, yv) = q.top(); q.pop();

        auto push = [&](int x1, int y1, int x2, int y2){
            if(x1 < 0 || y1 < 0 || x2 < 0 || y2 < 0) return;
            if(x1 >=W || y1 >= H || x2 >=W || y2 >= H) return;
        
            if(!validH[y1][x1]) return;
            if(!validV[y2][x2]) return;
            
            // (x2,y1) must be the common point 
            // check validity
            if(x2-x1 < 0 || x2-x1 >= w ||y1-y2 < 0 || y1-y2 >= h){
                return;
            }
            if(grid[y1][x2] == '*'){
                res = true;
                return;
            }

            if(vis[x1][y1][x2][y2]) return;
            vis[x1][y1][x2][y2] = true;

            // vis.insert({x1,y1,x2,y2});
            q.push({x1,y1,x2,y2});
        };

        push(xh+1,yh,xv,yv);
        push(xh,yh+1,xv,yv);
        push(xh,yh,xv+1,yv);
        push(xh,yh,xv,yv+1);

        push(xh-1,yh,xv,yv);
        push(xh,yh-1,xv,yv);
        push(xh,yh,xv-1,yv);
        push(xh,yh,xv,yv-1);
    }

    if(grid[YH][XV] == '*'){
        res = true; 
    }
    if(res){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

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