Submission #882555

#	Time	Username	Problem	Language	Result	Execution time	Memory
882555		ThylOne	Evacuation plan (IZhO18_plan)	C++14	0 / 100	208 ms	95292 KiB

plan

    //####################
    //IZHO_2018_Plan
    //####################
    #include<bits/stdc++.h>
    /*
    Plan
    Djikstra OK
    KRUSKAL  
    LCA
    SPARSE-TABLE
    */
    #define int long long
    using namespace std;
    const int INF=1e18;
    const int maxiNode = 2*100*1000;
    vector<pair<int,int>> links[maxiNode];
    struct UnionFind{
        vector<int> chef;
        UnionFind(int _size){
            chef.resize(_size);
            for(int i=0;i<_size;i++){
                chef[i]=i;
            }
        }
        int find(int a){
            if(chef[a]==a)return a;
            else return chef[a]=find(chef[a]);
        }
        bool fusion(int a,int b){
            int ra = find(a);
            int rb = find(b);
            if(ra!=rb){
                chef[ra]=rb;
                return true;
            }else{
                return false;
            }
        }
    };
    int minimal_distance[maxiNode];
    bool comp(pair<int,int> &a,pair<int,int> &b){
        int ra = min(minimal_distance[a.first],minimal_distance[a.second]);
        int rb = min(minimal_distance[b.first],minimal_distance[b.second]);
        return ra>rb;
    }
    vector<int> linksTree[maxiNode];
     
    const int LOG = 20;
    int up[LOG][maxiNode];
    int depth[maxiNode];
    void root_the_tree(int node,int dad=-1,int deep=0){
        up[0][node]=dad;
        depth[node]=deep;
        for(int v:linksTree[node])if(dad!=v){
            root_the_tree(v,node,deep+1);
        }
    }
    int getKancestor(int node,int k){
        for(int b=LOG-1;b>=0;b--){
            if((k>>b)&1){
                node = up[b][node];
                if(node==-1)return -1;
            }
        }
        return node;
    }
    int lca(int a,int b){
        if(depth[a]<depth[b])swap(a,b);
        a=getKancestor(a,depth[a]-depth[b]);
        if(a==b){
            return a;
        }else{
            for(int l = LOG-1 ; l>=0 ; l--){
                if(up[l][a] != up[l][b]){
                    a = up[l][a];
                    b = up[l][b];
                }
            }
            return up[0][a];
        }
    }
    int mini[LOG][maxiNode];
    int getMini(int node,int k){
        int re = mini[0][node];
        for(int i=0;i<k-1;i++){
            node=up[0][node];
            re = minimal_distance[node];
        }
        return re;
    }
    int ans;
    void findA(int a,int b,int minimum=INF,int dad=-1){
        minimum=min(minimum,minimal_distance[a]);
        if(a==b){
            ans=minimum;
            return;
        }
        for(int v:linksTree[a]){
            if(v!=dad){
                findA(v,b,minimum,a);
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        int n,m;cin>>n>>m;
        vector<pair<int,int>> edges;
        for(int i = 0;i<m;i++){
            int a,b,w;
            cin>>a>>b>>w;
            a--;b--;
            links[a].push_back({b,w});
            links[b].push_back({a,w});
            edges.push_back({a,b});
        }
        int k;cin>>k;
        vector<int> infected(k);
        for(int i=0;i<k;i++){
            cin>>infected[i];
            infected[i]--;
        }
        //Djikstra multi-source
        priority_queue<pair<int,int>> PQ;
        for(int i=0;i<k;i++){
            PQ.push({-0,infected[i]});
        }
        
        fill(minimal_distance,minimal_distance+n,-1);
        while(!PQ.empty()){
            pair<int,int> act = PQ.top();
            PQ.pop();
            if(minimal_distance[act.second]!=-1){
                continue;
            }else{
                minimal_distance[act.second] = act.first * -1;
                for(auto p:links[act.second]){
                    PQ.push({(minimal_distance[act.second]+p.second)*-1,p.first});
                }
            }
        }
        UnionFind UF(n);
        sort(edges.begin(),edges.end(),comp);
        for(int i=0;i<m;i++){
            pair<int,int> &act = edges[i];
            if(UF.fusion(act.first,act.second)){
               // cout<<act.first<<' '<<act.second<<endl;
                linksTree[act.first].push_back(act.second);
                linksTree[act.second].push_back(act.first);
            }
        }
        
        root_the_tree(0);
     
        for(int l=1;l<LOG;l++){
            for(int i=0;i<n;i++){
                if(up[l-1][i]==-1){
                    up[l][i]=-1;
                    continue;
                }
                up[l][i] = up[l-1][up[l-1][i]];
            }
        }
        for(int i=0;i<n;i++){
            mini[0][i] = minimal_distance[i];
        }
        for(int l=1;l<LOG;l++){
            for(int i=0;i<n;i++){
                if(up[l-1][i]==-1){
                    mini[l][i]=mini[l-1][i];
                    continue;
                }
                mini[l][i] = min(mini[l-1][i],mini[l-1][up[l-1][i]]);
            }
        }
        
        int q;cin>>q;
        for(int i=0;i<q;i++){
            int a,b;cin>>a>>b;
            a--;
            b--;
            int LCA = lca(a,b);
            int ans = INF;
            ans = min(ans, getMini(a,depth[a]-depth[LCA]));
            ans = min(ans, getMini(b,depth[b]-depth[LCA]));
           
            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