Submission #1291996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291996		haha	Evacuation plan (IZhO18_plan)	C++20	0 / 100	431 ms	46584 KiB

plan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INFLL = (ll)4e18;
const int MAXN = 100000 + 5;
const int LOG = 20;

int n, m;
vector<pair<int,int>> g[MAXN];
ll dis_arr[MAXN];

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

// DSU for Kruskal
int dsu[MAXN], dsu_sz[MAXN];
int find_set(int x){
    if(dsu[x]==x) return x;
    return dsu[x] = find_set(dsu[x]);
}
bool union_set(int a, int b){
    a = find_set(a); b = find_set(b);
    if(a==b) return false;
    if(dsu_sz[a] < dsu_sz[b]) swap(a,b);
    dsu[b] = a;
    dsu_sz[a] += dsu_sz[b];
    return true;
}

// MST adjacency (undirected)
vector<pair<int,ll>> mst[MAXN];

// HLD / LCA structures
int parentArr[MAXN];
int up[MAXN][LOG];
int depthArr[MAXN];
int sz[MAXN];

int ChainHead[MAXN], ChainID[MAXN], posInBase[MAXN], baseArr[MAXN];
int CurChain = 0, CurPos = 0;
ll aVal[MAXN]; // stores dis value for each node

// segment tree (min)
vector<ll> seg;
int baseN = 0;

void dijkstra_multi_source(const vector<int>& srcs){
    for(int i=1;i<=n;i++) dis_arr[i] = INFLL;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    for(int s: srcs){
        dis_arr[s] = 0;
        pq.push({0, s});
    }
    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        ll d = cur.first; int u = cur.second;
        if(d != dis_arr[u]) continue;
        for(auto &e : g[u]){
            int v = e.first; int w = e.second;
            if(dis_arr[v] > d + w){
                dis_arr[v] = d + w;
                pq.push({dis_arr[v], v});
            }
        }
    }
}

// DFS to prepare sizes, up[v][0], depth, parentArr
void dfs_prep(int u, int p){
    parentArr[u] = p;
    up[u][0] = p;
    sz[u] = 1;
    for(auto &e : mst[u]){
        int v = e.first;
        ll w = e.second; // weight stored but we use aVal for node values
        if(v == p) continue;
        depthArr[v] = depthArr[u] + 1;
        dfs_prep(v, u);
        sz[u] += sz[v];
    }
}

// HLD: assign chain/head/pos/baseArr
void HLD(int u, int p){
    if(ChainHead[CurChain] == 0) ChainHead[CurChain] = u;
    ChainID[u] = CurChain;
    posInBase[u] = ++CurPos;
    baseArr[CurPos] = u;

    int heavy = -1;
    for(auto &e : mst[u]){
        int v = e.first;
        if(v == p) continue;
        if(heavy == -1 || sz[v] > sz[heavy]) heavy = v;
    }
    if(heavy != -1) HLD(heavy, u);
    for(auto &e : mst[u]){
        int v = e.first;
        if(v == p || v == heavy) continue;
        CurChain++;
        HLD(v, u);
    }
}

// segment tree helpers
void seg_init(int nbase){
    baseN = nbase;
    seg.assign(4 * (baseN+5), INFLL);
}
void seg_build(int id, int l, int r){
    if(l == r){
        int node = baseArr[l];
        seg[id] = aVal[node];
        return;
    }
    int mid = (l+r)/2;
    seg_build(id*2, l, mid);
    seg_build(id*2+1, mid+1, r);
    seg[id] = min(seg[id*2], seg[id*2+1]);
}
ll seg_query(int id, int l, int r, int ql, int qr){
    if(ql > r || qr < l) return INFLL;
    if(ql <= l && r <= qr) return seg[id];
    int mid = (l+r)/2;
    return min(seg_query(id*2, l, mid, ql, qr), seg_query(id*2+1, mid+1, r, ql, qr));
}

// LCA (binary lifting) - requires up[][] precomputed
int lca(int u, int v){
    if(depthArr[u] < depthArr[v]) swap(u,v); // u deeper
    int diff = depthArr[u] - depthArr[v];
    for(int j=0;j<LOG;j++){
        if(diff & (1<<j)) u = up[u][j];
    }
    if(u == v) return u;
    for(int j=LOG-1;j>=0;j--){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }
    return up[u][0];
}

// Query min of aVal on path u--v excluding LCA node itself (matches original HLD intention)
// Returns INFLL if no nodes considered (e.g., u==v)
ll query_path_min_exclude_lca(int u, int v){
    int p = lca(u,v);
    ll ans = INFLL;

    // bring u up to p, chain by chain
    while(ChainID[u] != ChainID[p]){
        int head = ChainHead[ChainID[u]];
        ans = min(ans, seg_query(1, 1, baseN, posInBase[head], posInBase[u]));
        // jump to parent of head
        u = up[head][0];
    }
    // same chain: exclude p itself
    if(posInBase[p] + 1 <= posInBase[u]){
        ans = min(ans, seg_query(1, 1, baseN, posInBase[p] + 1, posInBase[u]));
    }

    // bring v up to p
    while(ChainID[v] != ChainID[p]){
        int head = ChainHead[ChainID[v]];
        ans = min(ans, seg_query(1, 1, baseN, posInBase[head], posInBase[v]));
        v = up[head][0];
    }
    if(posInBase[p] + 1 <= posInBase[v]){
        ans = min(ans, seg_query(1, 1, baseN, posInBase[p] + 1, posInBase[v]));
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        g[i].clear();
        mst[i].clear();
    }

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

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

    // multi-source dijkstra
    dijkstra_multi_source(sources);

    // build edges with weight = min(dist[u], dist[v]) (only once per undirected edge)
    edges.clear();
    for(int u=1; u<=n; u++){
        for(auto &e : g[u]){
            int v = e.first;
            if(u < v){
                edges.push_back({u, v, min(dis_arr[u], dis_arr[v])});
            }
        }
    }

    sort(edges.begin(), edges.end(), [](const Edge &A, const Edge &B){
        return A.w > B.w; // maximum spanning
    });

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

    // Kruskal -> MST (maximum spanning forest)
    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});
        }
    }

    // prepare arrays
    for(int i=1;i<=n;i++){
        parentArr[i] = 0;
        depthArr[i] = 0;
        sz[i] = 0;
        for(int j=0;j<LOG;j++) up[i][j] = 0;
        ChainHead[i] = 0;
        ChainID[i] = 0;
        posInBase[i] = 0;
        baseArr[i] = 0;
        aVal[i] = dis_arr[i]; // node value
    }
    CurChain = 1; CurPos = 0;

    // run DFS prep and HLD for all components (forest)
    for(int i=1;i<=n;i++){
        if(depthArr[i] == 0){
            depthArr[i] = 1;
            dfs_prep(i, 0);
            HLD(i, 0);
            CurChain++;
        }
    }

    // build binary lifting up[][] using parentArr (we set up[][0] = parentArr)
    // note: up[][] currently has up[v][0] = parentArr[v] = set in dfs_prep (which used parent)
    for(int j=1;j<LOG;j++){
        for(int v=1; v<=n; v++){
            int mid = up[v][j-1];
            if(mid == 0) up[v][j] = 0;
            else up[v][j] = up[mid][j-1];
        }
    }

    // build segtree on base size = CurPos
    int bN = CurPos;
    if(bN == 0){
        // no nodes? safety
        bN = n;
    }
    seg_init(bN);
    seg_build(1, 1, bN);

    // queries
    int Qq;
    cin >> Qq;
    while(Qq--){
        int u,v; cin >> u >> v;
        // if u and v not in same MST component, there's no path in the MST
        if(find_set(u) != find_set(v)){
            cout << -1 << '\n';
            continue;
        }
        ll ans = query_path_min_exclude_lca(u, v);
        if(ans == INFLL) cout << -1 << '\n';
        else cout << ans << '\n';
    }

    return 0;
}

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