Submission #1291597

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291597		haha	Evacuation plan (IZhO18_plan)	C++20	100 / 100	297 ms	58364 KiB

plan

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

using ll = long long;
const ll INF = (1LL << 60);
const int MAXN = 100000;

int n, m;
vector<pair<int,int>> adj[MAXN+5];  // (neighbor, weight)
ll dist_npp[MAXN+5];

struct Edge {
    int u, v;
    ll w;
};
vector<Edge> edges;

// DSU
int parent[MAXN+5], sz[MAXN+5];
int find_set(int v){
    if(v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}
bool union_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a == b) return false;
    if(sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
    return true;
}

vector<pair<int,ll>> mst[MAXN+5];
int up[MAXN+5][20];
ll mn[MAXN+5][20];
int depth[MAXN+5];

void dfs(int v, int p){
    for(auto [to, w] : mst[v]){
        if(to == p) continue;
        depth[to] = depth[v] + 1;
        up[to][0] = v;
        mn[to][0] = w;
        dfs(to, v);
    }
}

ll query(int u, int v){
    if(find_set(u) != find_set(v)) return 0;

    ll res = INF;

    if(depth[u] < depth[v]) swap(u, v);

    // lift u up
    int diff = depth[u] - depth[v];
    for(int k = 19; k >= 0; k--){
        if(diff & (1<<k)){
            res = min(res, mn[u][k]);
            u = up[u][k];
        }
    }

    if(u == v) return res;

    for(int k = 19; k >= 0; k--){
        if(up[u][k] != up[v][k]){
            res = min(res, mn[u][k]);
            res = min(res, mn[v][k]);
            u = up[u][k];
            v = up[v][k];
        }
    }

    res = min(res, mn[u][0]);
    res = min(res, mn[v][0]);
    return res;
}

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

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

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

    // Multi-source Dijkstra
    fill(dist_npp, dist_npp+n+1, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;

    for(int g : sources){
        dist_npp[g] = 0;
        pq.push({0, g});
    }

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

    // Build edges with weights = min(dist[u], dist[v])
    for(int u = 1; u <= n; u++){
        for(auto [v, w] : adj[u]){
            if(u < v){
                edges.push_back({u, v, min(dist_npp[u], dist_npp[v])});
            }
        }
    }

    // Sort edges decreasing
    sort(edges.begin(), edges.end(), [](Edge &a, Edge &b){
        return a.w > b.w;
    });

    // Init DSU
    for(int i = 1; i <= n; i++){
        parent[i] = i;
        sz[i] = 1;
    }

    // Build Maximum Spanning Tree
    for(auto &e : edges){
        if(union_set(e.u, e.v)){
            mst[e.u].push_back({e.v, e.w});
            mst[e.v].push_back({e.u, e.w});
        }
    }

    // LCA preprocess
    for(int i = 1; i <= n; i++){
        for(int k = 0; k < 20; k++){
            up[i][k] = 0;
            mn[i][k] = INF;
        }
    }

    // DFS from all components
    for(int i = 1; i <= n; i++){
        if(depth[i] == 0){
            depth[i] = 1;
            dfs(i, 0);
        }
    }

    // Build binary lifting
    for(int k = 1; k < 20; k++){
        for(int v = 1; v <= n; v++){
            int mid = up[v][k-1];
            up[v][k] = up[mid][k-1];
            mn[v][k] = min(mn[v][k-1], mn[mid][k-1]);
        }
    }

    // Answer queries
    int Q;
    cin >> Q;
    while(Q--){
        int s, t;
        cin >> s >> t;
        cout << query(s, t) << "\n";
    }

    return 0;
}

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