Hypyt

#include <iostream>
#include <unordered_map>
#include <string.h> // memset
#include <vector>
#include <ctime>


typedef unsigned char uchar;



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

    std::vector<uchar> rows[250];
    std::vector<uchar> columns[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] == '.') {
                rows[i].push_back(j);
                columns[j].push_back(i);
                //std::cout << "Connect row idx " << i << " to column idx " << j << std::endl;
            }
        }
    }
    std::clock_t input_complete_time = std::clock();

    
    std::vector<uchar> just_added_rows;
    std::vector<uchar> just_added_cols;
    just_added_rows.reserve(height);
    just_added_cols.reserve(width);

    bool available_rows[250];
    bool available_cols[250];

    std::vector<uchar> cols_to_add;    
    cols_to_add.reserve(width);
    
    std::string output;

    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;
        }

        memset(&available_rows, 0, height);
        memset(&available_cols, 0, width);

        //memset(&just_added_rows, 0, height);
        //memset(&just_added_cols, 0, width);

        just_added_rows.clear();
        just_added_cols.clear();

        just_added_rows.push_back(start_y);
        just_added_cols.push_back(start_x);

        cols_to_add.clear();
        for (int cost = 2;; 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;

            for (uchar row_idx : just_added_rows) {
                if (available_rows[row_idx]) { continue; }
                
                //std::cout << "Row " << (int) row_idx << std::endl;
                //just_added_rows[row_idx] = false;
                available_rows[row_idx] = true;

                // if no cols to add, don't set no_solution to false
                no_solution = no_solution && rows[row_idx].size() == 0;

                for (uchar col_idx : rows[row_idx]) {
                    if (available_cols[col_idx]) { continue; }

                    if (col_idx == end_x) {
                        output.append(std::to_string(cost));
                        output.push_back('\n');
                        goto complete;
                    }
                    //std::cout << "Add col " << (int) col_idx << std::endl;
                    cols_to_add.push_back(col_idx);
                }
            }
            just_added_rows.clear();

            for (uchar col_idx : just_added_cols) {
                if (available_cols[col_idx]) { continue; }

                //std::cout << "Col " << (int) col_idx << std::endl;
                //just_added_cols[col_idx] = false;
                available_cols[col_idx] = true;

                // if no cols to add, don't set no_solution to false
                no_solution = no_solution && columns[col_idx].size() == 0;

                for (uchar row_idx : columns[col_idx]) {
                    if (available_rows[row_idx]) { continue; }

                    if (row_idx == end_y) {
                        output.append(std::to_string(cost));
                        output.push_back('\n');
                        goto complete;
                    }
                    //std::cout << "Add row " << (int) row_idx << std::endl;
                    just_added_rows.push_back(row_idx);
                }
            }
            just_added_cols.clear();

            if (no_solution) {
                output.append("-1\n");
                // store network map for use in later calls
                for (uchar i = 0; i < 250; i++) {
                    if (available_cols[i]) {
                        networks[i] = cur_network_num;
                    }
                }
                cur_network_num++;
                goto complete;
            }

            while (cols_to_add.size()) {
                just_added_cols.push_back(cols_to_add.back());
                cols_to_add.pop_back();
            }
        }
complete:
        continue;
    }
    std::cout << output;

    std::clock_t complete_time = std::clock();

    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: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

Test 13

Group: 4, 5

Verdict: WRONG ANSWER

Test 14

Group: 4, 5

Verdict: WRONG ANSWER

Test 15

Group: 5

Verdict: WRONG ANSWER

Test 16

Group: 5

Verdict: WRONG ANSWER

Test 17

Group: 5

Verdict: WRONG ANSWER

Test 18

Group: 5

Verdict: WRONG ANSWER

Test 19

Group: 5

Verdict: WRONG ANSWER

Test 20

Group: 5

Verdict: WRONG ANSWER

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 23

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 24

Group: 5

Verdict: WRONG ANSWER

Test 25

Group: 5

Verdict: WRONG ANSWER

Test 26

Group: 5

Verdict: WRONG ANSWER

Test 27

Group: 5

Verdict: WRONG ANSWER