Submission #1189244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189244		Zakir060	Evacuation plan (IZhO18_plan)	C++20	0 / 100	315 ms	16880 KiB

plan

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>
#include <map> // Can be used instead of large vector for mid_bucket if needed

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; // 10^8 + 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];

// Initialize DSU: each node is its own parent
void init_dsu() {
    iota(parent + 1, parent + n + 1, 1); // Fill parent[i] = i for i from 1 to n
}

// Find the representative (root) of the set containing node v (with path compression)
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]); // Path compression
}

// Unite the sets containing nodes a and b
void unite_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        // Simple union: make one root point to the other.
        // Union by rank/size could be used but often not critical here.
        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];
int ans[MAXQ]; // Though L[i] will hold the final answer after loops

// Vector to store queries grouped by their 'mid' value in each iteration
// We use a vector of pairs (mid, query_index) and sort it instead of large array/map
vector<pair<int, int>> mid_query_pairs;

int main() {
    // Faster I/O
    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); // Store for later processing
    }

    // --- Read NPP locations and run Multi-Source Dijkstra ---
    cin >> k;
    vector<int> npp_cities(k);
    // Priority queue for Dijkstra: {distance, city}
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    // Initialize distances to infinity
    fill(dist_npp + 1, dist_npp + n + 1, INF);

    // Add all NPP cities to the priority queue with distance 0
    for (int i = 0; i < k; ++i) {
        cin >> npp_cities[i];
        if (dist_npp[npp_cities[i]] == INF) { // Handle case if same city has multiple NPPs (problem says no)
             dist_npp[npp_cities[i]] = 0;
             pq.push({0, npp_cities[i]});
        }
    }

    // Dijkstra algorithm
    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // If we found a shorter path already, skip
        if (d > dist_npp[u]) continue;

        // Relax edges
        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); // Reserve space
    int max_possible_threshold = 0; // Track the maximum threshold seen
    for(const auto& edge_tuple : raw_edges) {
        int u, v, w;
        tie(u, v, w) = edge_tuple;
        // Calculate threshold, handle potential INF distances (though graph is connected)
        long long threshold_ll = min(dist_npp[u], dist_npp[v]);
        int threshold_int = (threshold_ll >= MAX_DIST_THRESHOLD) ? MAX_DIST_THRESHOLD : (int)threshold_ll;
         if (threshold_ll == INF) threshold_int = 0; // Or handle appropriately if unreachable from NPP is possible

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

    // --- 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;                      // Lower bound for dangerousness
        R[i] = max_possible_threshold + 1; // Upper bound (exclusive)
    }

    // --- Parallel Binary Search ---
    // We perform a fixed number of iterations (logarithmic in the range of answers)
    // log2(10^8) is roughly 27, so 30-35 iterations are safe.
    for (int iter = 0; iter < 35; ++iter) {
        init_dsu(); // Reset DSU for this iteration
        mid_query_pairs.clear(); // Clear the list of mid-values to check

        // Group queries by their mid-value for this iteration
        for (int i = 0; i < Q; ++i) {
            if (L[i] != R[i]) { // If the range hasn't converged
                int mid = L[i] + (R[i] - L[i]) / 2;
                mid_query_pairs.push_back({mid, i});
            }
        }

        // If no queries left to process, break early
        if (mid_query_pairs.empty()) break;

        // Sort queries by their 'mid' value descending, to process them alongside edges
        sort(mid_query_pairs.rbegin(), mid_query_pairs.rend()); // Sort descending by mid

        int edge_idx = 0;
        int mid_pair_idx = 0;

        // Iterate through possible thresholds (mid values) from high to low implicitly via sorted lists
        // This loop structure efficiently processes edges and queries together
        for(const auto& edge : edges) {
             int current_edge_threshold = edge.threshold;

             // Process all queries whose 'mid' is >= the current edge's threshold
             while(mid_pair_idx < mid_query_pairs.size() && mid_query_pairs[mid_pair_idx].first >= current_edge_threshold) {
                 int query_idx = mid_query_pairs[mid_pair_idx].second;
                 int mid = mid_query_pairs[mid_pair_idx].first;
                 int s = queries[query_idx].s;
                 int t = queries[query_idx].t;

                 // Check connectivity *at the state before adding the current edge*
                 // This check happens when the DSU includes all edges with threshold > mid
                 // (Or >= mid, depending on strictness needed - need >= mid)
                 // Check if s and t can be connected with dangerousness 'mid'
                 if (dist_npp[s] >= mid && dist_npp[t] >= mid && find_set(s) == find_set(t)) {
                     L[query_idx] = mid; // Possible to achieve 'mid', try higher or equal
                 } else {
                     R[query_idx] = mid; // Not possible to achieve 'mid', must try lower
                 }
                 mid_pair_idx++;
             }

             // Add the current edge to the DSU
             unite_sets(edge.u, edge.v);
        }

         // Process any remaining queries (those with mid < smallest edge threshold, or mid=0)
         // These queries are checked against the DSU state after all edges have been added.
         while(mid_pair_idx < mid_query_pairs.size()) {
              int query_idx = mid_query_pairs[mid_pair_idx].second;
              int mid = mid_query_pairs[mid_pair_idx].first;
              int s = queries[query_idx].s;
              int t = queries[query_idx].t;

               // Check connectivity in the fully merged DSU (for edges relevant to the threshold)
              if (dist_npp[s] >= mid && dist_npp[t] >= mid && find_set(s) == find_set(t)) {
                   L[query_idx] = mid;
              } else {
                   R[query_idx] = mid;
              }
              mid_pair_idx++;
         }
    } // End of binary search iterations

    // --- Output Results ---
    // After the iterations, L[i] holds the maximum 'mid' for which the check succeeded,
    // which is the maximal dangerousness.
    for (int i = 0; i < Q; ++i) {
        cout << L[i] << "\n";
    }

    return 0;
}

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