Hypyt

#include <iostream>
#include <unordered_map>
#include <string.h> // memset
#include <vector>
#include <ctime>
#include <fstream>
 
 
typedef unsigned char uchar;


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

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

// 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 void bmp_print(bitmap &map) {
    std::cout << std::hex << map.values[3] << map.values[2] << map.values[1] << map.values[0] << std::endl;
}*/

// gets abouttiarallaa where to start iterating to find all values of 1
inline uchar bmp_get_start_index(bitmap &map) {
    for (uchar i = 0; i < BITMAP_WIDTH; i++) {
        if (map.values[i]) {
            uchar j = 0;
            while (!((uchar*) &map.values[i])[j++]) {}
            return i * BITMAP_VALUE_SIZE + (j-1) * 8;
        }
    }
    return 0; // doesnt matter what we return here, the loop will break instalty anyway
}

inline uchar bmp_get_end_index(bitmap &map) {
    for (uchar i = BITMAP_WIDTH-1; i >= 0; i++) {
        if (map.values[i]) {
            uchar j = 8;
            while (!((uchar*) &map.values[i])[--j]) {}
            return i * BITMAP_VALUE_SIZE + j * 8;
        }
    }
    return 0; // doesnt matter what we return here, the loop will break instalty anyway
 
}

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

    //std::ifstream input("in.txt");
    //std::ofstream output_stream("out.txt");
    
    
    bitmap rows[250];
    bitmap columns[250];
    memset(&rows, 0, sizeof(bitmap) * 250);
    memset(&columns, 0, sizeof(bitmap) * 250);
 
    // what is connected (and not connected) to what?
    // speeds up calculations resulting in -1
    // index with column_index or x
    int networks[250];
    memset(&networks, -1, 250 * sizeof(int));
 
    int cur_network_num = 0;
 
    std::cin >> height >> width >> query_count;
    //std::clock_t start_time = std::clock();
 
    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(rows[i], j);
                bmp_set(columns[j], i);
                //std::cout << "Connect row idx " << i << " to column idx " << j << std::endl;
            }
        }
    }
    //std::clock_t input_complete_time = std::clock();
 
    
    bitmap just_added_rows;
    bitmap just_added_cols;
    bmp_clear(just_added_rows);
    bmp_clear(just_added_cols);
    
    bitmap available_rows;
    bitmap available_cols;
    bmp_clear(available_rows);
    bmp_clear(available_cols);
 
    bitmap cols_to_add;    
    bmp_clear(cols_to_add);
    
    std::string output;
    output.reserve(query_count * 2);
 
    unsigned short start_y, start_x, end_y, end_x;
    //std::vector<std::clock_t> query_begin_times;
    for (unsigned long i = 0; i < query_count; i++) {
        //query_begin_times.push_back(std::clock());
        
        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) {
            output.append("0\n");
            continue;
        }
 
        if (start_x == end_x || start_y == end_y) {
            output.append("1\n");
            continue;
        }
 
        // if both are -1, neither are set already, we can't do anything with that info
        // if one is not -1, we know they are not in the same network or else the
        // code that set the other to not be -1 would have set them both to not be -1
        if (networks[start_x] != networks[end_x] && (networks[start_x] != -1 || networks[end_x] != -1)) {
            output.append("-1\n");
            continue;
        }
 
        bmp_clear(available_rows);
        bmp_clear(available_cols);
        
        //memset(&just_added_rows, 0, height);
        //memset(&just_added_cols, 0, width);
 
        bmp_clear(just_added_rows);
        bmp_clear(just_added_cols);
 
        bmp_set(just_added_rows, start_y);
        bmp_set(just_added_cols, start_x);
 
        bmp_clear(cols_to_add);
        for (int cost = 1;; cost++) {
        
            // set to false when modifying rows_to_add and cols_to_add, if no modifications are made then break out with -1
            //bool no_solution = true;
 
            //bmp_print(just_added_rows);
            //bmp_print(just_added_cols);
            for (uchar row_idx = bmp_get_start_index(just_added_rows); bmp_bool(just_added_rows); row_idx++) {
                if (!bmp_is_set(just_added_rows, row_idx)) { continue; }
                bmp_set_zero(just_added_rows, row_idx);
                
                if (bmp_is_set(available_rows, row_idx)) { continue; }
                
                //std::cout << "Row " << (int) row_idx << std::endl;
                //just_added_rows[row_idx] = false;
                bmp_set(available_rows, row_idx);
 
                //if (no_solution && bmp_bool(rows[row_idx])) { no_solution = false; }

                bitmap difference = bmp_exclude(rows[row_idx], available_cols);
                bmp_or(cols_to_add, difference);
            }
            //bmp_clear(just_added_rows);
 
            for (uchar col_idx = bmp_get_start_index(just_added_cols); bmp_bool(just_added_cols); col_idx++) {
                if (!bmp_is_set(just_added_cols, col_idx)) { continue; }
                bmp_set_zero(just_added_cols, col_idx);
                if (bmp_is_set(available_cols, col_idx)) { continue; }
 
                //std::cout << "Col " << (int) col_idx << std::endl;
                //just_added_cols[col_idx] = false;
                bmp_set(available_cols, col_idx);
 
                //if (no_solution && bmp_bool(columns[col_idx])) { no_solution = false; }

                bitmap difference = bmp_exclude(columns[col_idx], available_rows);
                bmp_or(just_added_rows, difference);
            }
            //bmp_clear(just_added_cols);

            if (bmp_is_set(available_rows, end_y) || bmp_is_set(available_cols, end_x)) {
                output.append(std::to_string(cost));
                output.push_back('\n');
                goto complete;
            }
 
            if (!bmp_bool(cols_to_add) && !bmp_bool(just_added_rows)) {
                output.append("-1\n");
                // store network map for use in later calls
                for (uchar i = bmp_get_start_index(available_cols); i < bmp_get_end_index(available_cols); i++) {
                    if (bmp_is_set(available_cols, i)) {
                        networks[i] = cur_network_num;
                    }
                }
                cur_network_num++;
                goto complete;
            }
 
            bmp_or(just_added_cols, cols_to_add);
            bmp_clear(cols_to_add);
        }
complete:
        continue;
    }
    //std::clock_t complete_time = std::clock();
    std::cout << output;
    
    //input.close();
    //output_stream.close();
 
 
    /*
    std::cout << "First split (input parsing) completed in " << (input_complete_time - start_time) / (double) CLOCKS_PER_SEC << std::endl;
    std::cout << "Processing completed in " << (complete_time - input_complete_time) / (double) CLOCKS_PER_SEC << std::endl;
    std::cout << "Program finished in " << (complete_time - start_time) / (double) CLOCKS_PER_SEC << std::endl;
    std::cout << "\nExtrapolated time splits:\n";
    std::cout << "First split (input parsing) completed in " << (100*input_complete_time - 100*start_time) / (double) CLOCKS_PER_SEC << std::endl;
    std::cout << "Processing completed in " << (100*complete_time - 100*input_complete_time) / (double) CLOCKS_PER_SEC << std::endl;
    std::cout << "Program finished in " << (100*complete_time - 100*start_time) / (double) CLOCKS_PER_SEC << std::endl;
    //*/
    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: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

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: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED