Submission #1241144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241144		aminabouakaz	Circle Passing (EGOI24_circlepassing)	C++20	0 / 100	853 ms	3684 KiB

Main

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>
long long dist_circ(long long u, long long v, long long N_total) {
    long long d = std::abs(u - v);
    return std::min(d, N_total - d);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long N, M, Q;
    std::cin >> N >> M >> Q;

    long long N_total = 2 * N; // Total number of students

    std::vector<long long> bf_map(N_total, -1);
    for (int i = 0; i < M; ++i) {
        long long k;
        std::cin >> k;
        bf_map[k] = k + N;
        bf_map[k + N] = k;
    }

    for (int q_idx = 0; q_idx < Q; ++q_idx) {
        long long x, y;
        std::cin >> x >> y;

        long long min_passes = dist_circ(x, y, N_total);


        if (bf_map[x] != -1) {
            min_passes = std::min(min_passes, 1 + dist_circ(bf_map[x], y, N_total));
        }
        
        if (bf_map[y] != -1) {
            min_passes = std::min(min_passes, 1 + dist_circ(x, bf_map[y], N_total));
        }
        if (bf_map[x] != -1 && bf_map[y] != -1) {
            min_passes = std::min(min_passes, 2 + dist_circ(bf_map[x], bf_map[y], N_total));
        }

        long long nx1 = (x - 1 + N_total) % N_total;
        long long nx2 = (x + 1) % N_total;

        if (bf_map[nx1] != -1) {
            min_passes = std::min(min_passes, 2 + dist_circ(bf_map[nx1], y, N_total));
        }
        if (bf_map[nx2] != -1) {
            min_passes = std::min(min_passes, 2 + dist_circ(bf_map[nx2], y, N_total));
        }
        long long ny1_bf = (bf_map[y] != -1) ? (bf_map[y] - 1 + N_total) % N_total : -1;
        long long ny2_bf = (bf_map[y] != -1) ? (bf_map[y] + 1) % N_total : -1;

        if (ny1_bf != -1 && bf_map[ny1_bf] != -1) { // if y has a bf and its neighbor has a bf
             min_passes = std::min(min_passes, 2 + dist_circ(x, bf_map[ny1_bf], N_total));
        }
        if (ny2_bf != -1 && bf_map[ny2_bf] != -1) { // if y has a bf and its neighbor has a bf
            min_passes = std::min(min_passes, 2 + dist_circ(x, bf_map[ny2_bf], N_total));
        }
        std::vector<long long> x_reach_2;
        x_reach_2.push_back(x);
        x_reach_2.push_back((x - 1 + N_total) % N_total);
        x_reach_2.push_back((x + 1) % N_total);
        if (bf_map[x] != -1) {
            x_reach_2.push_back(bf_map[x]);
        }
        
        std::vector<long long> current_x_set = {x};
        std::vector<long long> next_x_set;

        std::vector<long long> dist_from_x_small(N_total, -1);
        std::vector<long long> q_x;
        q_x.push_back(x);
        dist_from_x_small[x] = 0;
        int head = 0;

        while(head < q_x.size() && dist_from_x_small[q_x[head]] < 3) { // up to 2 passes away from x
            long long u = q_x[head++];
            long long d = dist_from_x_small[u];

            // Add neighbors
            long long v1 = (u - 1 + N_total) % N_total;
            long long v2 = (u + 1) % N_total;

            if (dist_from_x_small[v1] == -1) {
                dist_from_x_small[v1] = d + 1;
                q_x.push_back(v1);
            }
            if (dist_from_x_small[v2] == -1) {
                dist_from_x_small[v2] = d + 1;
                q_x.push_back(v2);
            }
            
            // Add best friend
            if (bf_map[u] != -1) {
                long long v_bf = bf_map[u];
                if (dist_from_x_small[v_bf] == -1) {
                    dist_from_x_small[v_bf] = d + 1;
                    q_x.push_back(v_bf);
                }
            }
        }

        std::vector<long long> interesting_nodes;
        interesting_nodes.push_back(x);
        interesting_nodes.push_back(y);
        
        if(bf_map[x] != -1) interesting_nodes.push_back(bf_map[x]);
        if(bf_map[y] != -1) interesting_nodes.push_back(bf_map[y]);

        long long x_minus_1 = (x - 1 + N_total) % N_total;
        long long x_plus_1 = (x + 1) % N_total;
        long long y_minus_1 = (y - 1 + N_total) % N_total;
        long long y_plus_1 = (y + 1) % N_total;

        interesting_nodes.push_back(x_minus_1);
        interesting_nodes.push_back(x_plus_1);
        interesting_nodes.push_back(y_minus_1);
        interesting_nodes.push_back(y_plus_1);

        if(bf_map[x_minus_1] != -1) interesting_nodes.push_back(bf_map[x_minus_1]);
        if(bf_map[x_plus_1] != -1) interesting_nodes.push_back(bf_map[x_plus_1]);
        if(bf_map[y_minus_1] != -1) interesting_nodes.push_back(bf_map[y_minus_1]);
        if(bf_map[y_plus_1] != -1) interesting_nodes.push_back(bf_map[y_plus_1]);

        std::sort(interesting_nodes.begin(), interesting_nodes.end());
        interesting_nodes.erase(std::unique(interesting_nodes.begin(), interesting_nodes.end()), interesting_nodes.end());


        std::vector<long long> start_nodes;
        std::vector<long long> end_nodes;
        std::map<long long, long long> dist_to_start;
        std::map<long long, long long> dist_to_end;

        start_nodes.push_back(x); dist_to_start[x] = 0;
        long long prev_x = (x - 1 + N_total) % N_total;
        long long next_x = (x + 1) % N_total;
        start_nodes.push_back(prev_x); dist_to_start[prev_x] = 1;
        start_nodes.push_back(next_x); dist_to_start[next_x] = 1;
        
        if (bf_map[x] != -1) {
            start_nodes.push_back(bf_map[x]);
            dist_to_start[bf_map[x]] = 1;
        }
        end_nodes.push_back(y); dist_to_end[y] = 0;
        long long prev_y = (y - 1 + N_total) % N_total;
        long long next_y = (y + 1) % N_total;
        end_nodes.push_back(prev_y); dist_to_end[prev_y] = 1;
        end_nodes.push_back(next_y); dist_to_end[next_y] = 1;
        
        if (bf_map[y] != -1) {
            end_nodes.push_back(bf_map[y]);
            dist_to_end[bf_map[y]] = 1;
        }
    
        for (long long s_node : start_nodes) {
            for (long long e_node : end_nodes) {
                min_passes = std::min(min_passes, dist_to_start[s_node] + dist_circ(s_node, e_node, N_total) + dist_to_end[e_node]);

            
                if (bf_map[s_node] != -1) {
                    min_passes = std::min(min_passes, dist_to_start[s_node] + 1 + dist_circ(bf_map[s_node], e_node, N_total) + dist_to_end[e_node]);
                }
                if (bf_map[e_node] != -1) {
                    min_passes = std::min(min_passes, dist_to_start[s_node] + dist_circ(s_node, bf_map[e_node], N_total) + 1 + dist_to_end[e_node]);
                }
                if (bf_map[s_node] != -1 && bf_map[e_node] != -1) {
                    min_passes = std::min(min_passes, dist_to_start[s_node] + 1 + dist_circ(bf_map[s_node], bf_map[e_node], N_total) + 1 + dist_to_end[e_node]);
                }
            }
        }

        std::cout << min_passes << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27