Submission #1123420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123420		serifefedartar	Toy (CEOI24_toy)	C++20	100 / 100	482 ms	102884 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 1600;

int W, H, hor, ver, ver_col, ver_row, hor_col, hor_row;
int par[10000000], sz[10000000];
vector<int> row_X[MAXN], col_X[MAXN];
string grid[MAXN];

int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    sz[a] += sz[b];
    par[b] = a;
}

void set_edges(int row, int col) {
    int dr[] = {-1, 0, 1, 0};
    int dc[] = {0, -1, 0, 1};
    for (int i = 0; i < 4; i++) {
        int nr = dr[i] + row;
        int nc = dc[i] + col;

        if (nr < 1 || nc < 1 || nr > H || nc > W)
            continue;
        if (grid[nr][nc] == 'X')
            continue;

        if (dr[i] == 0) {
            int l = lower_bound(col_X[col].begin(), col_X[col].end(), row) - col_X[col].begin() - 1;
            int r = l + 1;
            l = col_X[col][l];
            r = col_X[col][r];

            int l2 = lower_bound(col_X[nc].begin(), col_X[nc].end(), row) - col_X[nc].begin() - 1;
            int r2 = l2 + 1;
            l2 = max(l, col_X[nc][l2]) + 1;
            r2 = min(r, col_X[nc][r2]) - 1;

            if (r2 - l2 + 1 >= ver)
                unite(row * 2000 + col, nr * 2000 + nc);

        } else {
            int l = lower_bound(row_X[row].begin(), row_X[row].end(), col) - row_X[row].begin() - 1;
            int r = l + 1;
            l = row_X[row][l];
            r = row_X[row][r];

            int l2 = lower_bound(row_X[nr].begin(), row_X[nr].end(), col) - row_X[nr].begin() - 1;
            int r2 = l2 + 1;
            l2 = max(l, row_X[nr][l2]) + 1;
            r2 = min(r, row_X[nr][r2]) - 1;

            if (r2 - l2 + 1 >= hor)
                unite(row * 2000 + col, nr * 2000 + nc);

        }
    }
}

int main() {
    fast;
    for (int i = 0; i < 10000000; i++)
        par[i] = i, sz[i] = 1;
    cin >> W >> H >> hor >> ver;
    cin >> hor_col >> hor_row >> ver_col >> ver_row;
    ver_col++; ver_row++; hor_col++; hor_row++;

    for (int i = 1; i <= H; i++) {
        cin >> grid[i];
        grid[i] = "#" + grid[i];
    }

    for (int i = 1; i <= H; i++)
        row_X[i].push_back(0);
    for (int i = 1; i <= W; i++)
        col_X[i].push_back(0);

    int value = 0;
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (grid[i][j] == 'X') {
                row_X[i].push_back(j);
                col_X[j].push_back(i);
            }

            if (grid[i][j] == '*')
                value = i * 2000 + j;
        }
    }

    for (int i = 1; i <= H; i++)
        row_X[i].push_back(W+1);
    for (int i = 1; i <= W; i++)
        col_X[i].push_back(H+1);

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (grid[i][j] != 'X')
                set_edges(i, j);
        }
    }

    if (find(value) == find(hor_row * 2000 + ver_col))
        cout << "YES\n";
    else
        cout << "NO\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