제출 #522117

#제출 시각아이디문제언어결과실행 시간메모리
522117inluminasEvacuation plan (IZhO18_plan)C++17
0 / 100
782 ms78056 KiB
#include"bits/stdc++.h" using namespace std; #define ll long long #define endl "\n" #define fastio ios_base::sync_with_stdio(false) #define inf LLONG_MAX struct id{ int val=0,u=0,v=0; }; const int lmt=5e5+10; int dis[lmt],par[lmt],mn[lmt][20],P[lmt][20],lvl[lmt]; vector<pair<int,int>>adj[lmt]; void dijkstra(int k){ set<pair<int,int>>q; for(int i=1;i<=k;i++){ int x; cin>>x; dis[x]=0; q.insert({0,x}); } while(!q.empty()){ int val=(*q.begin()).first,u=(*q.begin()).second; q.erase(q.begin()); if(val>dis[u]){ continue; } for(auto [w,v]:adj[u]){ if(dis[u]+w<dis[v]){ dis[v]=dis[u]+w; q.insert({dis[v],v}); } } } return; } int findpar(int u){ if(par[u]==u) return u; return par[u]=findpar(par[u]); } void dfs(int u,int p){ for(auto [w,v]:adj[u]){ if(v==p) continue; lvl[v]=lvl[u]+1; mn[v][0]=w,P[v][0]=u; dfs(v,u); } } int lca(int p,int q){ if(lvl[p]<lvl[q]) swap(p,q); int pmn=INT_MAX,qmn=INT_MAX; for(int i=19;i>=0;i--){ if(lvl[p]-(1<<i)>=lvl[q]){ pmn=min(pmn,mn[p][i]); p=P[p][i]; } } if(p==q) return min(pmn,qmn); for(int i=19;i>=0;i--){ if(P[p][i]!=-1 && P[p][i]!=P[q][i]){ pmn=min(pmn,mn[p][i]),qmn=min(qmn,mn[q][i]); p=P[p][i],q=P[q][i]; } } pmn=min(pmn,mn[p][0]),qmn=min(qmn,mn[q][0]); return min(pmn,qmn); } int main(){ fastio; for(int i=0;i<lmt;i++) dis[i]=INT_MAX; int n,m; cin>>n>>m; vector<id>e; for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; e.push_back({0,u,v}); adj[u].push_back({w,v}); adj[v].push_back({w,u}); } int k; cin>>k; dijkstra(k); for(auto& x:e){ x.val=min(dis[x.u],dis[x.v]); } sort(e.begin(),e.end(),[](id x,id y){ return x.val>=y.val; }); for(int i=1;i<=n;i++){ par[i]=i; adj[i].clear(); } for(auto x:e){ int u=findpar(x.u), v=findpar(x.v); if(u==v) continue; par[u]=v; adj[x.u].push_back({x.val,x.v}); adj[x.v].push_back({x.val,x.u}); } for(int i=0;i<=n;i++){ for(int j=0;j<20;j++){ P[i][j]=-1,mn[i][j]=INT_MAX; } } dfs(1,0); for(int j=1;j<20;j++){ for(int i=1;i<=n;i++){ if(P[i][j-1]!=-1){ P[i][j]=P[P[i][j-1]][j-1]; mn[i][j]=min(mn[i][j-1],mn[P[i][j-1]][j-1]); } } } int q; cin>>q; while(q--){ int u,v; cin>>u>>v; cout<<lca(u,v)<<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...