Submission #1070546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070546		vjudge1	Toy (CEOI24_toy)	C++17	100 / 100	226 ms	111336 KiB

Main

#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));
    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) right[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 (stderr)

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