제출 #1273337

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273337		HuyAT	Evacuation plan (IZhO18_plan)	C++20	100 / 100	352 ms	73936 KiB

plan

#include<bits/stdc++.h>
#define newl '\n'

const int N = 1e5 + 10;
const int V = 1e7 + 10;
const long long INF = 1e18;
const long long M = 1e9 + 7;

template<int B>
struct LCA{
    int n;
    std::vector<std::vector<std::pair<int,long long>>> adj;
    std::vector<std::vector<int>> par;
    std::vector<std::vector<long long>> lift_min;
    std::vector<int> d;
    LCA(int n,std::vector<std::vector<std::pair<int,long long>>> adj) :
        n(n),
        adj(adj),par(n + 1,std::vector<int>(B + 1,0)),
        lift_min(n + 1,std::vector<long long>(B + 1,0)),d(n + 1,0){
//        std::cout << "IMP " << n << " " << B << newl;
        dfs();
        prepare();
//        std::cerr << "IMP " << lift_min[6][2] << newl;
    }
    void dfs(int u = 1){
        for(std::pair<int,long long> nxt : adj[u]){
            int v = nxt.first;
            long long w = nxt.second;
            if(v == par[u][0]){
                continue;
            }
            par[v][0] = u;
            lift_min[v][0] = w;
            d[v] = d[u] + 1;
            dfs(v);
        }
    }
    void prepare(){
        par[1][0] = 1;
        lift_min[1][0] = INF;
//        std::cout << "IMP " << n << newl;
        for(int j = 1;j <= B;++j){
            for(int i = 1;i <= n;++i){
                par[i][j] = par[par[i][j - 1]][j - 1];
                lift_min[i][j] = std::min(lift_min[i][j - 1],lift_min[par[i][j - 1]][j - 1]);
            }
        }
    }
    long long get_min(int u,int v){
        if(d[u] < d[v]){
            std::swap(u,v);
        }
        long long ans = INF;
        for(int i = B;i >= 0;--i){
            if(d[par[u][i]] >= d[v]){
                ans = std::min(ans,lift_min[u][i]);
                u = par[u][i];
            }
        }
        if(u == v){
            return ans;
        }
        for(int i = B;i >= 0;--i){
            if(par[u][i] != par[v][i]){
                ans = std::min(ans,lift_min[u][i]);
                ans = std::min(ans,lift_min[v][i]);
                u = par[u][i];
                v = par[v][i];
            }
        }
        ans = std::min(ans,lift_min[u][0]);
        ans = std::min(ans,lift_min[v][0]);
        return ans;
    }
};
struct DSU{
    std::vector<int> lab;
    DSU(int n) : lab(n + 1,-1){

    }
    int find_set(int i){
        return (lab[i] < 0 ? i : lab[i] = find_set(lab[i]));
    }
    bool same_set(int x,int y){
        return (find_set(x) == find_set(y));
    }
    void merg(int x,int y){
        x = find_set(x);
        y = find_set(y);
        if(x == y){
            return;
        }
        if(-lab[x] > -lab[y]){
            std::swap(x,y);
        }
        lab[y] += lab[x];
        lab[x] = y;
    }
};
struct Solver{
    static const int B = 20;
    struct Data{
        int u;
        long long w;
        bool operator > (const Data &other) const {
            return (w > other.w);
        }
    };
    int n,m,k,q;
    std::vector<std::vector<std::pair<int,int>>> adj;
    std::vector<int> nuclear_city;
    std::vector<std::pair<int,int>> edge;
    std::vector<long long> f;
    Solver(){

    }
    void readData(){
        std::cin >> n >> m;
        f = std::vector<long long>(n + 1,0);
        adj = std::vector<std::vector<std::pair<int,int>>>(n + 1);
        edge = std::vector<std::pair<int,int>>(m + 1,{0,0});
        for(int i = 1;i <= m;++i){
            int u,v,w;
            std::cin >> u >> v >> w;
            adj[u].emplace_back(v,w);
            adj[v].emplace_back(u,w);
            edge[i] = {u,v};
        }
        std::cin >> k;
        for(int i = 1;i <= k;++i){
            int v;
            std::cin >> v;
            nuclear_city.emplace_back(v);
        }
        std::cin >> q;
    }
    void dijkstra(){
        std::fill(f.begin(),f.end(),INF);
        std::priority_queue<Data,std::vector<Data>,std::greater<Data>> pq;
        for(int u : nuclear_city){
            f[u] = 0;
            pq.push({u,f[u]});
        }
        while(!pq.empty()){
            Data t = pq.top();
            pq.pop();
            if(t.w > f[t.u]){
                continue;
            }
            for(std::pair<int,int> nxt : adj[t.u]){
                int v = nxt.first;
                int w = nxt.second;
                if(f[t.u] + w < f[v]){
                    f[v] = f[t.u] + w;
                    pq.push({v,f[v]});
                }
            }
        }
    }
    LCA<B> build_tree(){
        DSU graph(n);
        std::vector<std::vector<std::pair<int,long long>>> tree_adj(n + 1);
        auto cmp = [&](std::pair<int,int> lhs,std::pair<int,int> rhs){
            return std::min(f[lhs.first],f[lhs.second]) > std::min(f[rhs.first],f[rhs.second]);
        };
        std::sort(edge.begin() + 1,edge.end(),cmp);
        for(int i = 1;i <= m;++i){
            std::pair<int,int> cur = edge[i];
            if(!graph.same_set(cur.first,cur.second)){
                long long w = std::min(f[cur.first],f[cur.second]);
                graph.merg(cur.first,cur.second);
                tree_adj[cur.first].emplace_back(cur.second,w);
                tree_adj[cur.second].emplace_back(cur.first,w);
//                std::cout << cur.first << " " << cur.second << " " << w << newl;
            }
        }
        return LCA<B>(n,tree_adj);
    }
    void solve(){
        LCA<B> tree = build_tree();
        for(int i = 1;i <= q;++i){
            int s,t;
            std::cin >> s >> t;
            std::cout << tree.get_min(s,t) << newl;
        }
    }
    void main(){
        readData();
        dijkstra();
        solve();
    }
};

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    Solver().main();
    return 0;
}

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