Submission #882531

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

signed main(){
    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<<endl;
    }
    
    
    
    return 0;
};

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