Submission #1291593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291593		haha	Evacuation plan (IZhO18_plan)	C++20	23 / 100	253 ms	36992 KiB

plan

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int s, t, id;
};

int n, m, k, Q;
vector<pair<int,long long>> adj[100005]; // w là long long
long long dist[100005];
bool active[100005];
int parent[100005], sz[100005];

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

void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a,b);
    parent[b] = a;
    sz[a] += sz[b];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for(int i=1;i<=n;i++){
        parent[i] = i;
        sz[i] = 1;
        active[i] = false;
    }

    for(int i=0;i<m;i++){
        int u,v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    cin >> k;
    vector<int> sources(k);
    for(int i=0;i<k;i++) cin >> sources[i];

    // Multi-source Dijkstra
    for(int i=1;i<=n;i++) dist[i] = LLONG_MAX;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
    for(int g : sources){
        dist[g] = 0;
        pq.push({0,g});
    }

    while(!pq.empty()){
        auto [d,u] = pq.top(); pq.pop();
        if(d != dist[u]) continue;
        for(auto [v,w] : adj[u]){
            if(dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v],v});
            }
        }
    }

    cin >> Q;
    vector<Query> queries(Q);
    for(int i=0;i<Q;i++){
        cin >> queries[i].s >> queries[i].t;
        queries[i].id = i;
    }

    // Sắp xếp node theo dist giảm
    vector<int> nodes(n);
    iota(nodes.begin(), nodes.end(), 1);
    sort(nodes.begin(), nodes.end(), [&](int a,int b){ return dist[a] > dist[b]; });

    // Tính key cho mỗi query = min(dist[s], dist[t])
    vector<pair<long long,int>> query_order(Q); // {key, query_index}
    for(int i=0;i<Q;i++){
        long long key = min(dist[queries[i].s], dist[queries[i].t]);
        query_order[i] = {key,i};
    }

    // Sắp xếp query giảm theo key
    sort(query_order.rbegin(), query_order.rend());

    vector<long long> ans(Q);
    int idx_node = 0;
    for(auto &[key, idx] : query_order){
        // Kích hoạt tất cả node có dist >= key
        while(idx_node < n && dist[nodes[idx_node]] >= key){
            int v = nodes[idx_node];
            active[v] = true;
            for(auto &[u,w] : adj[v]){
                if(active[u]) union_set(v,u);
            }
            idx_node++;
        }
        // Sau khi union xong, kiểm tra query
        int s = queries[idx].s, t = queries[idx].t;
        if(find_set(s) == find_set(t)) ans[idx] = key;
        else ans[idx] = 0;
    }

    for(int i=0;i<Q;i++) cout << ans[i] << "\n";

    return 0;
}

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