oj.uz

Submission #1088614

# Submission time Handle Problem Language Result Execution time Memory
1088614 2024-09-14T16:48:35 Z nikd Toy (CEOI24_toy) C++17
0 / 100
 16 ms 2876 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;
            }
        }
    }

    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:119:17: warning: 'i_obj' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |     if(sol[i_obj][j_obj]) cout << "YES\n";
      |                 ^

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 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 1 ms 432 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 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 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 436 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 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 1 ms 432 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 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 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 436 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 6 ms 2092 KB Output is correct
5 Correct 5 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 16 ms 2192 KB Output is correct
8 Correct 14 ms 2196 KB Output is correct
9 Correct 5 ms 956 KB Output is correct
10 Correct 16 ms 2396 KB Output is correct
11 Correct 16 ms 2392 KB Output is correct
12 Correct 4 ms 1116 KB Output is correct
13 Correct 12 ms 2876 KB Output is correct
14 Correct 12 ms 2648 KB Output is correct
15 Correct 4 ms 1884 KB Output is correct
16 Correct 4 ms 2140 KB Output is correct
17 Correct 5 ms 1884 KB Output is correct
18 Correct 4 ms 2140 KB Output is correct
19 Correct 4 ms 2140 KB Output is correct
20 Correct 4 ms 2140 KB Output is correct
21 Correct 4 ms 2136 KB Output is correct
22 Correct 4 ms 2088 KB Output is correct
23 Correct 4 ms 1980 KB Output is correct
24 Correct 4 ms 2136 KB Output is correct
25 Correct 8 ms 1996 KB Output is correct
26 Correct 6 ms 2136 KB Output is correct
27 Correct 6 ms 2140 KB Output is correct
28 Correct 6 ms 2140 KB Output is correct
29 Correct 6 ms 2140 KB Output is correct
30 Correct 3 ms 1884 KB Output is correct
31 Correct 4 ms 1884 KB Output is correct
32 Correct 4 ms 1984 KB Output is correct
33 Correct 4 ms 1880 KB Output is correct
34 Correct 3 ms 1884 KB Output is correct
35 Correct 4 ms 1884 KB Output is correct
36 Correct 6 ms 2396 KB Output is correct
37 Correct 4 ms 1884 KB Output is correct
38 Correct 4 ms 1884 KB Output is correct
39 Correct 4 ms 1884 KB Output is correct
40 Correct 4 ms 1884 KB Output is correct
41 Correct 4 ms 1884 KB Output is correct
42 Correct 4 ms 1996 KB Output is correct
43 Correct 4 ms 1984 KB Output is correct
44 Correct 4 ms 2140 KB Output is correct
45 Correct 4 ms 2140 KB Output is correct
46 Incorrect 4 ms 2652 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 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 1 ms 432 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 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 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 436 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 0 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 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 432 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 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 1 ms 432 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 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 1 ms 348 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 436 KB Output is correct
44 Correct 1 ms 344 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Incorrect 0 ms 348 KB Output isn't correct
47 Halted 0 ms 0 KB -