oj.uz

Submission #1088617

# Submission time Handle Problem Language Result Execution time Memory
1088617 2024-09-14T16:57:03 Z nikd Toy (CEOI24_toy) C++17
0 / 100
 5 ms 2396 KB 
#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--;
                }
                
            }
        }
    }

    /*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)&&t[i_v+1][j_v]==-1&&t[i_v][j_v]!=-1){
            t[i_v+1][j_v] = t[i_v][j_v]+1;
            q.push({i_v+1, j_v});
        }
        if(isvalid(i_v-1, j_v)&&b[i_v-1][j_v]==-1&&b[i_v][j_v]!=-1){
            b[i_v-1][j_v] = b[i_v][j_v]+1;
            q.push({i_v-1, j_v});
        }
        if(isvalid(i_v, j_v+1)&&l[i_v][j_v+1]==-1&&l[i_v][j_v]!=-1){
            l[i_v][j_v+1] = l[i_v][j_v]+1;
            q.push({i_v, j_v+1});
        }
        if(isvalid(i_v, j_v-1)&&r[i_v][j_v-1]==-1&&r[i_v][j_v]!=-1){
            r[i_v][j_v-1] = r[i_v][j_v]+1;
            q.push({i_v, j_v-1});
        }  
    }*/

    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;

    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

Main.cpp: In function 'int main()':
Main.cpp:141:17: warning: 'i_obj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     if(sol[i_obj][j_obj]) cout << "YES\n";
      |                 ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 388 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 388 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1884 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 5 ms 1884 KB Output is correct
8 Correct 4 ms 1884 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 4 ms 2140 KB Output is correct
11 Correct 4 ms 2140 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 5 ms 2140 KB Output is correct
14 Correct 5 ms 2140 KB Output is correct
15 Correct 3 ms 1884 KB Output is correct
16 Correct 3 ms 1920 KB Output is correct
17 Correct 3 ms 1884 KB Output is correct
18 Correct 3 ms 1884 KB Output is correct
19 Correct 4 ms 1884 KB Output is correct
20 Correct 4 ms 1884 KB Output is correct
21 Correct 4 ms 1884 KB Output is correct
22 Correct 3 ms 2064 KB Output is correct
23 Correct 3 ms 1884 KB Output is correct
24 Correct 4 ms 2076 KB Output is correct
25 Correct 4 ms 1884 KB Output is correct
26 Correct 4 ms 1860 KB Output is correct
27 Correct 4 ms 1884 KB Output is correct
28 Correct 4 ms 1884 KB Output is correct
29 Correct 4 ms 1884 KB Output is correct
30 Correct 3 ms 1884 KB Output is correct
31 Correct 3 ms 1884 KB Output is correct
32 Correct 4 ms 1880 KB Output is correct
33 Correct 3 ms 1884 KB Output is correct
34 Correct 3 ms 1880 KB Output is correct
35 Correct 4 ms 1884 KB Output is correct
36 Correct 3 ms 1884 KB Output is correct
37 Correct 3 ms 1884 KB Output is correct
38 Correct 3 ms 1884 KB Output is correct
39 Correct 3 ms 1884 KB Output is correct
40 Correct 3 ms 1884 KB Output is correct
41 Correct 3 ms 1884 KB Output is correct
42 Correct 3 ms 1880 KB Output is correct
43 Correct 3 ms 1884 KB Output is correct
44 Correct 4 ms 1884 KB Output is correct
45 Correct 3 ms 1884 KB Output is correct
46 Incorrect 5 ms 2396 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 388 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 388 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Halted 0 ms 0 KB -