Submission #1047986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047986		PurpleCrayon	Toy (CEOI24_toy)	C++17	100 / 100	308 ms	383708 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1.5e3+10, MOD = 1e9+7;
const int INF = 2e9+10;

vector<vector<int>> can_square(vector<vector<int>> g, int a, int b) {
    int n = sz(g), m = sz(g[0]);
    auto can = g;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!g[i][j]) continue;

            int k = j;
            while (k < m && g[i][k]) k++;
            k--;
            
            for (int me = j; me <= k; me++) {
                can[i][me] &= (k - j + 1) >= a;
            }

            j = k;
        }
    }

    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            if (!g[i][j]) continue;

            int k = i;
            while (k < n && g[k][j]) k++;
            k--;

            for (int me = i; me <= k; me++) {
                can[me][j] &= (k - i + 1) >= b;
            }

            i = k;
        }
    }

    /*
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!g[i][j]) continue;

            int ra = 1;
            for (int k = j-1; k >= 0; k--) {
                if (!g[i][k]) break;
                ra++;
            }
            for (int k = j+1; k < m; k++) {
                if (!g[i][k]) break;
                ra++;
            }

            int rb = 1;
            for (int k = i-1; k >= 0; k--) {
                if (!g[k][j]) break;
                rb++;
            }
            for (int k = i+1; k < n; k++) {
                if (!g[k][j]) break;
                rb++;
            }

            if (ra >= a && rb >= b) {
                can[i][j] = 1;
            }
        }
    }
    */

    return can;
}
 
int n, m, a, b;
bool vis[N][N];

void dfs(int i, int j, const auto& one, const auto& two, const auto& can) {
    vis[i][j] = 1;
    if (i < n-1 && !vis[i+1][j] && can[i+1][j] && one[i][j]) {
        dfs(i+1, j, one, two, can);
    }
    if (j < m-1 && !vis[i][j+1] && can[i][j+1] && two[i][j]) {
        dfs(i, j+1, one, two, can);
    }
    if (i > 0 && !vis[i-1][j] && can[i-1][j] && one[i-1][j]) {
        dfs(i-1, j, one, two, can);
    }
    if (j > 0 && !vis[i][j-1] && can[i][j-1] && two[i][j-1]) {
        dfs(i, j-1, one, two, can);
    }
}

void solve() {
    cin >> m >> n >> a >> b;
    int trash, si, sj; cin >> trash >> si >> sj >> trash;

    vector<vector<int>> g(n, vector<int>(m));

    int ei = -1, ej = -1;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == 'X') g[i][j] = 0;
            else {
                g[i][j] = 1;
                if (s[j] == '*')
                    ei = i, ej = j;
            }
        }
    }

    vector<vector<int>> g1(n-1, vector<int>(m));
    vector<vector<int>> g2(n, vector<int>(m-1));
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < m; j++) {
            g1[i][j] = g[i][j] & g[i+1][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m-1; j++) {
            g2[i][j] = g[i][j] & g[i][j+1];
        }
    }

    auto one = can_square(g1, a, b-1), two = can_square(g2, a-1, b);
    auto can = can_square(g, a, b);
    if (!can[si][sj] || !can[ei][ej]) {
        cout << "NO\n";
        return;
    }

    dfs(si, sj, one, two, can);

    cout << (vis[ei][ej] ? "YES\n" : "NO\n");
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Compilation message (stderr)

Main.cpp:83:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   83 | void dfs(int i, int j, const auto& one, const auto& two, const auto& can) {
      |                              ^~~~
Main.cpp:83:47: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   83 | void dfs(int i, int j, const auto& one, const auto& two, const auto& can) {
      |                                               ^~~~
Main.cpp:83:64: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   83 | void dfs(int i, int j, const auto& one, const auto& two, const auto& can) {
      |                                                                ^~~~

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27