Submission #1289780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289780		i_love_kim_ji_won	Evacuation plan (IZhO18_plan)	C++20	0 / 100	115 ms	45508 KiB

plan

// I ♡ 김지원
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100000 + 5;
const int LG = 20;
const ll LINF = (ll)4e18;

struct Edge { int v; ll w; };
struct Edge3 { int u, v; ll w; };

vector<Edge> g[N]; // reused: first original graph, later MST adjacency
int U[200000 + 5], V[200000 + 5];
ll Worig[200000 + 5];
ll distArr[N];

struct Node {
    int u; ll d;
    bool operator<(Node const& other) const { return d > other.d; }
};

// DSU
int dsu_par[N], dsu_sz[N];
int find_set(int x){ return dsu_par[x]==x?x:dsu_par[x]=find_set(dsu_par[x]); }
bool unite_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_par[b] = a;
    dsu_sz[a] += dsu_sz[b];
    return true;
}

// LCA tables
int up[N][LG];
int depthArr[N];
ll mn[N][LG]; // mn[v][k] = min edge on path from v up to up[v][k]

// Multi-source Dijkstra
void multi_dijkstra(int n, const vector<int>& plants){
    // distArr assumed initialized to LINF outside
    priority_queue<Node> pq;
    for (int p : plants) pq.push({p, 0});
    while(!pq.empty()){
        auto cur = pq.top(); pq.pop();
        if (cur.d != distArr[cur.u]) continue;
        int u = cur.u;
        for (auto &e : g[u]){
            int v = e.v; ll w = e.w;
            if (distArr[v] > distArr[u] + w){
                distArr[v] = distArr[u] + w;
                pq.push({v, distArr[v]});
            }
        }
    }
}

// Build MST adjacency (by cap) then compute parent/depth/mn via BFS (iterative)
void build_lca_bfs(int n, int root){
    // visited array
    vector<char> vis(n+1, 0);
    queue<int> q;
    q.push(root);
    vis[root] = 1;
    depthArr[root] = 0;
    up[root][0] = 0;
    mn[root][0] = LINF;
    // initialize others already done before
    while(!q.empty()){
        int u = q.front(); q.pop();
        for (auto &e : g[u]){
            int v = e.v; ll w = e.w;
            if (vis[v]) continue;
            vis[v] = 1;
            depthArr[v] = depthArr[u] + 1;
            up[v][0] = u;
            mn[v][0] = w;
            // fill higher jumps for v
            for (int k = 1; k < LG; ++k){
                up[v][k] = up[ up[v][k-1] ][k-1];
                mn[v][k] = min(mn[v][k-1], mn[ up[v][k-1] ][k-1]);
            }
            q.push(v);
        }
    }
    // There might be multiple components (if MST didn't connect all) -> do BFS from any unvisited nodes
    for (int i = 1; i <= n; ++i){
        if (!vis[i]){
            vis[i] = 1;
            depthArr[i] = 0;
            up[i][0] = 0;
            mn[i][0] = LINF;
            for (int k = 1; k < LG; ++k){ up[i][k]=0; mn[i][k]=LINF; }
            q.push(i);
            while(!q.empty()){
                int u2 = q.front(); q.pop();
                for (auto &e : g[u2]){
                    int v = e.v; ll w = e.w;
                    if (vis[v]) continue;
                    vis[v] = 1;
                    depthArr[v] = depthArr[u2] + 1;
                    up[v][0] = u2;
                    mn[v][0] = w;
                    for (int k = 1; k < LG; ++k){
                        up[v][k] = up[ up[v][k-1] ][k-1];
                        mn[v][k] = min(mn[v][k-1], mn[ up[v][k-1] ][k-1]);
                    }
                    q.push(v);
                }
            }
        }
    }
}

int lca(int a, int b){
    if (a == b) return a;
    if (depthArr[a] < depthArr[b]) swap(a,b);
    int diff = depthArr[a] - depthArr[b];
    for (int i = 0; i < LG; ++i) if (diff >> i & 1) a = up[a][i];
    if (a == b) return a;
    for (int i = LG-1; i >= 0; --i){
        if (up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

ll jump_min(int u, int anc){
    if (u == anc) return LINF;
    ll res = LINF;
    int diff = depthArr[u] - depthArr[anc];
    for (int i = 0; i < LG; ++i){
        if (diff >> i & 1){
            res = min(res, mn[u][i]);
            u = up[u][i];
        }
    }
    return res;
}

ll query_path(int a, int b){
    if (a == b) return 0;
    if (find_set(a) != find_set(b)) return 0; // not connected in MST -> no path
    int L = lca(a,b);
    ll la = jump_min(a, L);
    ll lb = jump_min(b, L);
    ll ans = min(la, lb);
    if (ans == LINF) return 0;
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    if (!(cin >> n >> m)) return 0;

    // clear
    for (int i = 1; i <= n; ++i){
        g[i].clear();
        distArr[i] = LINF;
        dsu_par[i] = i;
        dsu_sz[i] = 1;
        depthArr[i] = 0;
        for (int k = 0; k < LG; ++k){
            up[i][k] = 0;
            mn[i][k] = LINF;
        }
    }

    for (int i = 1; i <= m; ++i){
        int a,b; ll w; cin >> a >> b >> w;
        U[i] = a; V[i] = b; Worig[i] = w;
        g[a].push_back({b,w});
        g[b].push_back({a,w});
    }

    int k; cin >> k;
    vector<int> plants;
    plants.reserve(k);
    for (int i = 0; i < k; ++i){
        int x; cin >> x;
        plants.push_back(x);
        distArr[x] = 0;
    }
    // run multi-source dijkstra
    multi_dijkstra(n, plants);

    // build edges with cap = min(dist[u], dist[v])
    vector<Edge3> edges; edges.reserve(m);
    for (int i = 1; i <= m; ++i){
        ll cap = min(distArr[U[i]], distArr[V[i]]);
        edges.push_back({U[i], V[i], cap});
    }
    sort(edges.begin(), edges.end(), [](const Edge3 &a, const Edge3 &b){ return a.w > b.w; });

    // clear adjacency to build MST
    for (int i = 1; i <= n; ++i) g[i].clear();
    int root = 1;
    for (auto &e : edges){
        if (unite_set(e.u, e.v)){
            continue; // already same component -> skip
        }
        // merged -> add to MST
        g[e.u].push_back({e.v, e.w});
        g[e.v].push_back({e.u, e.w});
        root = e.u;
    }

    // prepare LCA with BFS (iterative). Fill up[][] and mn[][]
    build_lca_bfs(n, root);

    int Q; cin >> Q;
    while (Q--){
        int s,t; cin >> s >> t;
        cout << query_path(s,t) << '\n';
    }
    return 0;
}

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