Hypyt

input/code.cpp: In function 'int main()':
input/code.cpp:181:31: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
  181 |     for (int query = 0; query < query_count; query++) {
      |                         ~~~~~~^~~~~~~~~~~~~

#include <iostream>
#include <string.h>
#include <vector>


typedef unsigned char uchar;


const int BITMAP_WIDTH = 4;
const int BITMAP_VALUE_SIZE = 64;

typedef struct bitmap {
    uint64_t values[4];
} bitmap;

typedef struct BoardState {
    bitmap rows;
    bitmap columns;
} BoardState;

inline constexpr int maxi(int a, int b) {
    return a > b ? a : b;
}

// a = a | b
inline void bmp_or(bitmap& first, bitmap& second) {
    for (int i = 0; i < BITMAP_WIDTH; i++) {
        first.values[i] |= second.values[i];
    }
}

// a & ~b
inline bitmap bmp_exclude(bitmap &first, bitmap& second) {
    bitmap map;
    for (int i = 0; i < BITMAP_WIDTH; i++) {
        map.values[i] = first.values[i] & ~second.values[i];
    }
    return map;
}

// a
inline bool bmp_bool(bitmap &map) {
    return map.values[0] || map.values[1] || map.values[2] || map.values[3];// || map.values[4] || map.values[5] || map.values[6] || map.values[7];
}

// a = a | (1<<b)
inline void bmp_set(bitmap &map, uchar shift_count) {
    map.values[shift_count / BITMAP_VALUE_SIZE] |= ((uint64_t) 1)<<(shift_count % BITMAP_VALUE_SIZE);
}

// a = a & ~(1<<b)
inline void bmp_set_zero(bitmap &map, uchar shift_count) {
    map.values[shift_count / BITMAP_VALUE_SIZE] &= ~(((uint64_t) 1)<<(shift_count % BITMAP_VALUE_SIZE));
}

// (bool) a & (1<<(b-1))
inline bool bmp_is_set(bitmap &map, uchar shift_count) {
    return map.values[shift_count / BITMAP_VALUE_SIZE] & ((uint64_t) 1)<<(shift_count % BITMAP_VALUE_SIZE);
}

// a = 0
inline void bmp_clear(bitmap &map) {
    memset(&map, 0, sizeof(uint64_t) * BITMAP_WIDTH);
}

inline bool bmp_neq(bitmap &first, bitmap &second) {
    for (int i = 0; i < BITMAP_WIDTH; i++) {
        if (first.values[i] != second.values[i]) {
            return true;
        }
    }
    return false;
}


inline BoardState step(BoardState &state, bitmap row_connections[250], bitmap col_connections[250]) {
    BoardState new_state = state;

    for (int row_idx = 0; row_idx < 250; row_idx++) {
        if (!bmp_is_set(state.rows, row_idx)) { continue; }
        bmp_or(new_state.columns, row_connections[row_idx]);
    }
    
    for (int col_idx = 0; col_idx < 250; col_idx++) {
        if (!bmp_is_set(state.columns, col_idx)) { continue; }
        bmp_or(new_state.rows, col_connections[col_idx]);
    }
    
    return new_state;
}

inline bool state_neq(BoardState *first, BoardState *second) {
    return (
        bmp_neq(first->columns, second->columns) ||
        bmp_neq(first->rows, second->rows)
    );
}

int main() {
    unsigned short height, width;
    unsigned long query_count;
    
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);

    bitmap row_connections[250];
    bitmap column_connections[250];
    memset(&row_connections, 0, sizeof(bitmap) * 250);
    memset(&column_connections, 0, sizeof(bitmap) * 250);

    std::vector<BoardState> row_states[250];
    std::vector<BoardState> column_states[250];
    
    int networks[250];
    memset(&networks, -1, 250 * sizeof(int));
 
    int cur_network_num = 0;
 
    std::cin >> height >> width >> query_count;

    
    for (unsigned short i = 0; i < height; i++) {
        char buf[251];
        std::cin >> buf;
 
        for (int j = 0; j < width; j++) {
            if (buf[j] == '.') {
                bmp_set(row_connections[i], j);
                bmp_set(column_connections[j], i);
            }
        }
    }

    // columns
    for (int i = 0; i < width; i++) {
        std::vector<BoardState> *cur_vec = &column_states[i];

        BoardState begin_state;
        
        bmp_clear(begin_state.columns);
        bmp_clear(begin_state.rows);

        bmp_set(begin_state.columns, i);

        cur_vec->push_back(begin_state);

        do {
            cur_vec->push_back(step(cur_vec->back(), row_connections, column_connections));
        } while (state_neq(&*(cur_vec->rbegin() + 1), &cur_vec->back()));

        // set networks from cols; no point in optimizing
        for (int i = 0; i < 250; i++) {
            if (bmp_is_set(cur_vec->back().columns, i)) {
                networks[i] = cur_network_num;
            }
        }
        cur_network_num++;
    }

    // rows
    for (int i = 0; i < height; i++) {
        std::vector<BoardState> *cur_vec = &row_states[i];

        BoardState begin_state;
        
        bmp_clear(begin_state.columns);
        bmp_clear(begin_state.rows);

        bmp_set(begin_state.rows, i);

        cur_vec->push_back(begin_state);

        do {
            cur_vec->push_back(step(cur_vec->back(), row_connections, column_connections));
        } while (state_neq(&*(cur_vec->rbegin() + 1), &cur_vec->back()));
    }

    
    unsigned short start_y, start_x, end_y, end_x;
    // actual checks
    for (int query = 0; query < query_count; query++) {
        std::cin >> start_y >> start_x >> end_y >> end_x;
        start_y--; start_x--; end_y--; end_x--;

        if (start_x == end_x && start_y == end_y) {
            std::cout << "0\n";
            goto complete;
        }

        if (start_x == end_x || start_y == end_y) {
            std::cout << "1\n";
            goto complete;
        }

        if (networks[start_x] != networks[end_x] && (networks[start_x] != -1 || networks[end_x] != -1)) {
            std::cout << "-1\n";
            goto complete;
        }

        {
            std::vector<BoardState> *row_state = &row_states[start_y];
            const int row_state_count = row_state->size();
            std::vector<BoardState> *col_state = &column_states[start_x];
            const int col_state_count = col_state->size();
            for (int idx = 0; idx < maxi(row_state_count, col_state_count); idx++) {
                
                if (idx < row_state_count) {
                    BoardState *state = &(*row_state)[idx];
                    if (
                        bmp_is_set(state->columns, end_x) ||
                        bmp_is_set(state->rows, end_y)
                    ) {
                        std::cout << idx + 1 << '\n';
                        goto complete;
                    }
                }
                if (idx < col_state_count) {
                    BoardState *state = &(*col_state)[idx];
                    if (
                        bmp_is_set(state->columns, end_x) ||
                        bmp_is_set(state->rows, end_y)
                    ) {
                        std::cout << idx + 1 << '\n';
                        goto complete;
                    }
                }
            }
            std::cout << "wut??";
        }
complete:
        continue;
    }


    return 0;
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

Test 13

Group: 4, 5

Verdict: ACCEPTED

Test 14

Group: 4, 5

Verdict: ACCEPTED

Test 15

Group: 5

Verdict: ACCEPTED

Test 16

Group: 5

Verdict: ACCEPTED

Test 17

Group: 5

Verdict: ACCEPTED

Test 18

Group: 5

Verdict: ACCEPTED

Test 19

Group: 5

Verdict: ACCEPTED

Test 20

Group: 5

Verdict: ACCEPTED

Test 21

Group: 5

Verdict: ACCEPTED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: ACCEPTED

Test 27

Group: 5

Verdict: ACCEPTED