제출 #1309330

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309330		anarch_y	Evacuation plan (IZhO18_plan)	C++20	100 / 100	470 ms	79320 KiB

plan

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

struct LCA{
    int n; 
    vector<vector<int>> adj, up, up_min;
    vector<int> depth, A;
    
    LCA(int _n){
        n = _n;
        up.resize(n+1);
        up_min.resize(n+1);
        for(int i=0; i<=n; i++){
            up[i].resize(20, 0);
            up_min[i].resize(20, 1e9);
        }
        adj.resize(n+1);
        depth.resize(n+1);
        A.resize(n+1);
    }

    void ae(int a, int b){
        adj[a].pb(b);
        adj[b].pb(a);
    }

    void dfs(int s, int p){
        depth[s] = depth[p]+1;
        up[s][0] = p;
        up_min[s][0] = A[s];
        for(auto u: adj[s]){
            if(u == p) continue;
            dfs(u, s);
        }
    }

    void init(){
        depth[0] = 0;
        dfs(1, 0);
        for(int j=1; j<20; j++){
            for(int i=1; i<=n; i++){
                up[i][j] = up[up[i][j-1]][j-1];
                up_min[i][j] = min(up_min[i][j-1], up_min[up[i][j-1]][j-1]);
            }
        }    
    }

    int jump(int x, int d){
        for(int i=0; i<20; i++){
            if(d & (1<<i)) x = up[x][i];
        }
        return x;
    }

    int jump_min(int x, int d){
        int mn = 1e9;
        for(int i=0; i<20; i++){
            if(d & (1<<i)){
                mn = min(mn, up_min[x][i]);
                x = up[x][i];
            }
        }
        return mn;
    }
    
    int lca(int a, int b){
        if(depth[a] < depth[b]) swap(a, b);
        a = jump(a, depth[a]-depth[b]);

        if(a == b) return a; 
        
        for(int i=19; i>=0; i--){
            if(up[a][i] != up[b][i]){
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
    
	int dist(int a, int b){
		int c = lca(a, b);
		int d = depth[a]+depth[b]-2*depth[c];
		return d;
	}
};

struct DSU{
    vector<int> link, size;
 
    DSU(int n){
        link.resize(n+1, 0);
        size.resize(n+1, 1);
        for(int i=1; i<=n; i++) link[i] = i;
    }
 
    int find(int x){
        if(x != link[x]) link[x] = find(link[x]);
        return link[x];
    }
 
    bool same(int a, int b){
        return find(a) == find(b);
    }
    
    void merge(int a, int b){
        if(same(a, b)) return;
        a = find(a); b = find(b);
        if(size[a] > size[b]) swap(a, b);
        link[a] = b;
        size[b] += size[a];
    }
};

const int maxn = 100001;
vector<pair<int, int>> adj[maxn];

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

    int n, m; cin >> n >> m;
    vector<pair<int, int>> edges;
    for(int i=0; i<m; i++){
        int a, b, c; cin >> a >> b >> c;
        adj[a].pb({b, c}); adj[b].pb({a, c});
        edges.pb({a, b});
    }
    int k; cin >> k;
    vector<int> v(k+1);
    for(int i=1; i<=k; i++) cin >> v[i];
    vector<int> dist(n+1, 1e9);
    using T = pair<int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for(int i=1; i<=k; i++){
        dist[v[i]] = 0;
        pq.push({0, v[i]});
    }
    while(!pq.empty()){
        auto [d, a] = pq.top(); pq.pop();
        if(d > dist[a]) continue;
        for(auto [b, w]: adj[a]){
            if(dist[b] > dist[a] + w){
                dist[b] = dist[a] + w;
                pq.push({dist[b], b});
            }
        }
    }
    vector<vector<int>> edges1;
    for(auto [a, b]: edges){
        int c = min(dist[a], dist[b]);
        edges1.pb({c, a, b});
    }
    sort(all(edges1), greater<>());
    LCA L(n);
    for(int i=1; i<=n; i++){
        L.A[i] = dist[i];
    } 
    DSU D(n);
    for(auto w: edges1){
        int a = w[1], b = w[2];
        if(!D.same(a, b)){
            D.merge(a, b);
            L.ae(a, b);
        }
    }
    L.init();
    int q; cin >> q;
    while(q--){
        int a, b; cin >> a >> b;
        int c = L.lca(a, b);
        int d1 = L.depth[a] - L.depth[c];
        int d2 = L.depth[b] - L.depth[c];
        int mn1 = L.jump_min(a, d1);
        int mn2 = L.jump_min(b, d2);
        int ans = min({mn1, mn2, L.A[c]});
        cout << ans << "\n";
    }
}

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