Submission #1189245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189245		Zakir060	Evacuation plan (IZhO18_plan)	C++20	100 / 100	1381 ms	37028 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <tuple> // For raw_edges

using namespace std;

// Define constants for array sizes and infinity
const long long INF = 1e18; // Use long long for distances
const int MAXN = 100005;
const int MAXM = 500005;
const int MAXQ = 100005;
// Maximum possible distance could be N * max_weight = 10^5 * 1000 = 10^8
// Define a safe upper bound for binary search range
const int MAX_DIST_THRESHOLD = 100000001; // Max possible threshold + 1

// Adjacency list to store the graph: pair<neighbor, weight>
vector<pair<int, int>> adj[MAXN];
// Array to store the minimum distance from each city to the nearest NPP
long long dist_npp[MAXN];
// Number of cities, roads, NPPs, and queries
int n, m, k, Q;

// --- Disjoint Set Union (DSU) ---
int parent[MAXN];

void init_dsu() {
    iota(parent + 1, parent + n + 1, 1);
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        parent[b] = a;
    }
}
// --- End DSU ---

// Structure to represent edges along with their safety threshold
struct Edge {
    int u, v;
    int threshold; // min(dist_npp[u], dist_npp[v])
};

// Comparison function for sorting edges by threshold descending
bool compareEdges(const Edge& a, const Edge& b) {
    return a.threshold > b.threshold;
}

// Structure to represent queries
struct Query {
    int s, t, id;
};

// Arrays to store the binary search range [L, R) and final answer for each query
int L[MAXQ], R[MAXQ];
// Final answer will be stored in L[i] after iterations

// Vector to store queries grouped by their 'mid' value in each iteration
vector<pair<int, int>> mid_query_pairs; // Stores {mid, query_original_index}

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

    // --- Read Graph ---
    cin >> n >> m;
    vector<tuple<int, int, int>> raw_edges; // Store edges temporarily
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        raw_edges.emplace_back(u, v, w);
    }

    // --- Read NPP locations and run Multi-Source Dijkstra ---
    cin >> k;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    fill(dist_npp + 1, dist_npp + n + 1, INF);

    for (int i = 0; i < k; ++i) {
        int npp_city;
        cin >> npp_city;
        if (dist_npp[npp_city] > 0) { // Add only if not already 0
             dist_npp[npp_city] = 0;
             pq.push({0, npp_city});
        }
    }

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > dist_npp[u]) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist_npp[u] + weight < dist_npp[v]) {
                dist_npp[v] = dist_npp[u] + weight;
                pq.push({dist_npp[v], v});
            }
        }
    }

    // --- Prepare Edges with Thresholds ---
    vector<Edge> edges;
    edges.reserve(m);
    int max_possible_threshold = 0;
    for(const auto& edge_tuple : raw_edges) {
        int u, v, w;
        tie(u, v, w) = edge_tuple;
        long long threshold_ll = min(dist_npp[u], dist_npp[v]);
        // Handle potential INF if a node is unreachable from any NPP (problem guarantees connectivity)
        int threshold_int = (threshold_ll >= MAX_DIST_THRESHOLD) ? (MAX_DIST_THRESHOLD -1) : (int)threshold_ll;
         if (threshold_ll == INF) continue; // Should not happen based on problem statement

        edges.push_back({u, v, threshold_int});
        max_possible_threshold = max(max_possible_threshold, threshold_int);
    }
    sort(edges.begin(), edges.end(), compareEdges); // Sort descending by threshold

    // --- Read Queries and Initialize Binary Search ---
    cin >> Q;
    vector<Query> queries(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> queries[i].s >> queries[i].t;
        queries[i].id = i;
        L[i] = 0;
        R[i] = max_possible_threshold + 1; // Upper bound (exclusive)
    }

    // --- Parallel Binary Search (Corrected Logic) ---
    for (int iter = 0; iter < 35; ++iter) { // ~log2(MaxDist) iterations
        init_dsu();
        mid_query_pairs.clear();

        for (int i = 0; i < Q; ++i) {
            if (L[i] != R[i]) {
                int mid = L[i] + (R[i] - L[i]) / 2;
                mid_query_pairs.push_back({mid, i});
            }
        }

        if (mid_query_pairs.empty()) break;

        sort(mid_query_pairs.rbegin(), mid_query_pairs.rend()); // Sort descending by mid

        int edge_idx = 0;

        for (const auto& mid_pair : mid_query_pairs) {
            int mid = mid_pair.first;
            int query_idx = mid_pair.second; // Original index of the query
            Query& q = queries[query_idx]; // Get s, t from original query structure

            // Add edges with threshold >= mid
            while (edge_idx < edges.size() && edges[edge_idx].threshold >= mid) {
                unite_sets(edges[edge_idx].u, edges[edge_idx].v);
                edge_idx++;
            }

            // Check connectivity for this query
            if (dist_npp[q.s] >= mid && dist_npp[q.t] >= mid && find_set(q.s) == find_set(q.t)) {
                L[query_idx] = mid; // Possible, try [mid, R)
            } else {
                R[query_idx] = mid; // Not possible, try [L, mid)
            }
        }
    } // End of binary search iterations

    // --- Output Results ---
    for (int i = 0; i < Q; ++i) {
        cout << L[i] << "\n";
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46