Submission #882792

#	Time	Username	Problem	Language	Result	Execution time	Memory
882792		ThylOne	Evacuation plan (IZhO18_plan)	C++14	100 / 100	773 ms	136540 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 b=LOG-1;b>=0;b--){
        if((k>>b)&1){
            re = min(re,mini[b][node]);
            
            node = up[b][node];
            if(node==-1)break;;
        }
    }
    re = min(re,minimal_distance[node]);
    return re;
}
        
int ans;

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);
        ans = INF;
        ans = min(ans, getMini(a,depth[a]-depth[LCA]));
        ans = min(ans, getMini(b,depth[b]-depth[LCA]));
        ans = min(ans,minimal_distance[a]);
        ans = min(ans,minimal_distance[b]);
    
        cout<<ans<<'\n';;
    }       
    return 0;
        };

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