Submission #1292000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292000		haha	Evacuation plan (IZhO18_plan)	C++20	100 / 100	575 ms	65852 KiB

plan

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

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

int n, m;
vector<pair<int,int>> adj[MAXN+5];  // (neighbor, weight)
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> Q;
ll dis[MAXN];
int sources[MAXN],dsu[MAXN];
int k;
struct Edge {
    int u, v;
    ll w;
};
vector<Edge> edges;

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

int Find(int u)
{
    if(u==dsu[u]) return u;
    int p=Find(dsu[u]);
    dsu[u]=p;
    return p;
}

bool join(int u,int v)
{
    u=Find(u);
    v=Find(v);
    if(u==v) return false;
    dsu[u]=v;
    return true;
}


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(u) != Find(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;
}

void dijkstra()
{
    for(int i=1;i<=n;i++) dis[i]=1e18;
    for(int i=0;i<k;i++){
        dis[sources[i]]=0;
        Q.push({0,sources[i]});
    }
    while(!Q.empty()){
        int u=Q.top().s;
        Q.pop();
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].f;
            int w=adj[u][i].s;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                Q.push({dis[v],v});
            }
        }
    }
}

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});
    }
    cin >> k;
    for(int i = 0; i < k; i++) cin >> sources[i];
    dijkstra();

    // Build edges with weights = min(dist[u], dist[v])
    for(int i=1;i<=n;i++) dsu[i]=i;
    for(int u=1;u<=n;u++){
        for(int i=0;i<adj[u].size();i++){
            int v=adj[u][i].f;
            edges.push_back({u,v,min(dis[u],dis[v])});
        }
    }
    sort(edges.begin(),edges.end(),[](Edge a, Edge b){
         return a.w>b.w;
    });

    for(int i = 1; i <= n; i++){
        dsu[i]=i;
    }

    // Build Maximum Spanning Tree
    for(int i=0;i<edges.size();i++){
        int u=edges[i].u;
        int v=edges[i].v;
        if(join(u,v)){
            mst[u].push_back({v,edges[i].w});
            mst[v].push_back({u,edges[i].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
    dfs(1,1);

    // 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