Submission #882522

#TimeUsernameProblemLanguageResultExecution timeMemory
882522ThylOneEvacuation plan (IZhO18_plan)C++14
0 / 100
725 ms71816 KiB
//#################### //IZHO_2018_Plan //#################### #include<bits/stdc++.h> /* Plan Djikstra OK KRUSKAL LCA SPARSE-TABLE */ using namespace std; const int INF=10000000; 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]); node = up[b][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){ 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; };
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...