Submission #1088620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088620		nikd	Toy (CEOI24_toy)	C++17	100 / 100	142 ms	50436 KiB

Main

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

int w,h;
vector<vector<bool>> sol;
vector<string> grid;

inline bool isvalid(int i, int j){
    return i<h&&j<w&& i>=0 && j>= 0 && sol[i][j]==0 && grid[i][j]!='X';
}

int main(){
    cin >> w >> h;
    int K, L; cin >> K >> L;
    int xh, yh, xv, yv; cin >> xh >> yh >> xv >> yv;
    grid.resize(h);
    for(int i = 0; i<h; i++) cin >> grid[i];
    sol.resize(h, vector<bool>(w, 0));

    vector<vector<int>> l(h, vector<int>(w, -1));
    vector<vector<int>> r(h, vector<int>(w, -1));
    vector<vector<int>> t(h, vector<int>(w, -1));
    vector<vector<int>> b(h, vector<int>(w, -1));

    queue<pair<int, int>> q;
    int i_obj, j_obj;
    for(int i = 0; i<h; i++){
        for(int j = 0; j<w; j++){
            if(grid[i][j]=='*'){
                i_obj = i; j_obj = j;
            }
            else if(grid[i][j]=='X'){
                q.push({i, j});
                l[i][j]=0;
                r[i][j]=0;
                t[i][j]=0;
                b[i][j]=0;
                int i2 = i; int j2 = j;
                i2++;
                while(isvalid(i2, j2)){
                    t[i2][j2]=t[i2-1][j2]+1;
                    i2++;
                }
                i2 = i; i2--;
                while(isvalid(i2, j2)){
                    b[i2][j2]=b[i2+1][j2]+1;
                    i2--;
                }
                i2 = i; j2++;
                while(isvalid(i2, j2)){
                    l[i2][j2]=l[i2][j2-1]+1;
                    j2++;
                }
                j2 = j; j2--;
                while(isvalid(i2, j2)){
                    r[i2][j2]=r[i2][j2+1]+1;
                    j2--;
                }
                
            }
        }
    }

    
    for(int i = 0; i<h; i++){
        for(int j = 0; j<w; j++){
            if(t[i][j]==-1) t[i][j]=i+1;
            if(b[i][j]==-1) b[i][j]=h-i;
            if(l[i][j]==-1) l[i][j]=j+1;
            if(r[i][j]==-1) r[i][j]=w-j;

        }
    }


    int i_start = yh; int j_start = xv;
    sol[i_start][j_start]=1;

    q.push({i_start, j_start});

    while(!q.empty()){
        auto pr = q.front();
        int i_v = pr.first;
        int j_v = pr.second;
        q.pop();
        if(isvalid(i_v+1, j_v)){
            int l_1 = min(l[i_v][j_v], l[i_v+1][j_v]);
            int r_1 = min(r[i_v][j_v], r[i_v+1][j_v]);
            if(r_1+l_1-1>=K){
                sol[i_v+1][j_v]=1;
                q.push({i_v+1, j_v});
            }
        }
        if(isvalid(i_v-1, j_v)){
            int l_1 = min(l[i_v][j_v], l[i_v-1][j_v]);
            int r_1 = min(r[i_v][j_v], r[i_v-1][j_v]);
            if(r_1+l_1-1>=K){
                sol[i_v-1][j_v]=1;
                q.push({i_v-1, j_v});
            }
        }
        if(isvalid(i_v, j_v+1)){
            int t_1 = min(t[i_v][j_v+1], t[i_v][j_v]);
            int b_1 = min(b[i_v][j_v+1], b[i_v][j_v]);
            if(b_1+t_1-1>=L){
                sol[i_v][j_v+1]=1;
                q.push({i_v, j_v+1});
            }
        }
        if(isvalid(i_v, j_v-1)){
            int t_1 = min(t[i_v][j_v-1], t[i_v][j_v]);
            int b_1 = min(b[i_v][j_v-1], b[i_v][j_v]);
            if(b_1+t_1-1>=L){
                sol[i_v][j_v-1]=1;
                q.push({i_v, j_v-1});
            }
        }
    }

    if(sol[i_obj][j_obj]) cout << "YES\n";
    else cout << "NO\n";
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:120:17: warning: 'i_obj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |     if(sol[i_obj][j_obj]) cout << "YES\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