oj.uz

답안 #1070513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1070513 2024-08-22T14:54:18 Z Alebn Toy (CEOI24_toy) C++14
0 / 100
 10 ms 4952 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

struct S {
    int x, y;
    S(){}
    S(int xi, int yi):x(xi),y(yi){}
};
int sum(vector<vector<int>>& prefix, int x1, int y1, int x2, int y2) {
    return prefix[x2][y2] - (x1 > 0 ? prefix[x1 - 1][y2] : 0) - (y1 > 0 ? prefix[x2][y1 - 1] : 0) + (x1 > 0 && y1 > 0 ? prefix[x1 - 1][y1 - 1] : 0);
}
int add(vector<vector<int>>& prefix, int i, int j) {
    return prefix[i][j] + (i > 0 ? prefix[i - 1][j] : 0) + (j > 0 ? prefix[i][j - 1] : 0) - (i > 0 && j > 0 ? prefix[i - 1][j - 1] : 0);
}

void solve() {
    int n, m, k, l, xh, yh, xv, yv, endx, endy;
    cin >> m >> n >> l >> k >> yh >> xh >> yv >> xv;
    vector<string> arr(n);
    vector<vector<int>> prefix(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        for(int j = 0; j < m; j++) {
            prefix[i][j] = (arr[i][j] == 'X') + add(prefix, i, j);
            if(arr[i][j] == '*') endx = i, endy = j;
        }
    }
    vector<vector<int>> up(n, vector<int>(m)), down(n, vector<int>(m)), right(n, vector<int>(m)), left(n, vector<int>(m));
    // calculate for hori
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(i > 0 && j > l - 2 && sum(prefix, i - 1, j - l + 1, i, j) == 0) {
                down[i - 1][j - l + 1]++;
                if(j < m - 2) down[i - 1][j + 1]--;
                up[i][j - l + 1]++;
                if(j < m - 2) up[i][j + 1]--;
            }
            if(i > k - 2 && j > 0 && sum(prefix, i - k + 1, j - 1, i, j) == 0) {
                right[i - k + 1][j - 1]++;
                if(i < n - 2) down[i + 1][j - 1]--;
                left[i - k + 1][j]++;
                if(i < n - 2) left[i + 1][j]--;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            up[i][j] += (j > 0 ? up[i][j - 1] : 0);
            down[i][j] += (j > 0 ? down[i][j - 1] : 0);
            right[i][j] += (i > 0 ? right[i - 1][j] : 0);
            left[i][j] += (i > 0 ? left[i - 1][j] : 0);
        }
    }
    queue<S> q;
    vector<vector<int>> visited(n, vector<int>(m, false));
    q.push(S(xh, yv));
    while(q.size()) {
        S temp = q.front();
        q.pop();
        if(visited[temp.x][temp.y]) continue;
        visited[temp.x][temp.y] = true;
        if(up[temp.x][temp.y]) q.push(S(temp.x - 1, temp.y));
        if(down[temp.x][temp.y]) q.push(S(temp.x + 1, temp.y));
        if(right[temp.x][temp.y]) q.push(S(temp.x, temp.y + 1));
        if(left[temp.x][temp.y]) q.push(S(temp.x, temp.y - 1));
    }
    if(visited[endx][endy]) cout << "YES\n";
    else cout << "NO\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:69:26: warning: 'endy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     if(visited[endx][endy]) cout << "YES\n";
      |                          ^
Main.cpp:69:20: warning: 'endx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     if(visited[endx][endy]) cout << "YES\n";
      |                    ^

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 4700 KB Output is correct
5 Correct 10 ms 4700 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 10 ms 4844 KB Output is correct
8 Correct 7 ms 4952 KB Output is correct
9 Correct 3 ms 1884 KB Output is correct
10 Correct 3 ms 4696 KB Output is correct
11 Correct 4 ms 4700 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 3 ms 4700 KB Output is correct
15 Correct 6 ms 4616 KB Output is correct
16 Incorrect 7 ms 4184 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 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 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Incorrect 0 ms 348 KB Output isn't correct
19 Halted 0 ms 0 KB -