제출 #334199

#제출 시각아이디문제언어결과실행 시간메모리
334199vipghn2003Evacuation plan (IZhO18_plan)C++14
22 / 100
555 ms68712 KiB
#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mp make_pair using namespace std; const int N=1e5+5; int n,m,d[N],s[N],t[N],l[N],r[N],res[N]; vector<pii>adj[N]; vector<int>query[N]; struct edge { int u,v,w; }; bool lf(edge a,edge b) { return a.w<b.w; } vector<edge>e; int p[N]; int Find(int x) { if(x==p[x]) return x; return p[x]=Find(p[x]); } void Union(int u,int v) { u=Find(u); v=Find(v); if(u==v) return ; p[u]=v; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; for(int i=1;i<=m;i++) { int u,v,w; cin>>u>>v>>w; adj[u].push_back(mp(v,w)); adj[v].push_back(mp(u,w)); e.push_back({u,v,w}); } memset(d,127,sizeof d); priority_queue<pii,vector<pii>,greater<pii>>pq; int k; cin>>k; while(k--) { int v; cin>>v; d[v]=0; pq.push(mp(0,v)); } while(!pq.empty()) { int u=pq.top().se; int dist=pq.top().fi; pq.pop(); if(d[u]!=dist) continue; for(auto&x:adj[u]) { int v=x.fi; int ndist=dist+x.se; if(d[v]>ndist) { d[v]=ndist; pq.push(mp(d[v],v)); } } } for(int i=0;i<m;i++) e[i].w=min(d[e[i].u],d[e[i].v]); sort(e.begin(),e.end(),lf); //for(auto&x:e) cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n'; int q; cin>>q; for(int i=1;i<=q;i++) { cin>>s[i]>>t[i]; l[i]=0; r[i]=m-1; } for(int rep=0;rep<=20;rep++) { iota(p+1,p+n+1,1); for(int i=0;i<m;i++) query[i].clear(); for(int i=1;i<=q;i++) { if(l[i]>r[i]) continue; int mid=(l[i]+r[i])/2; query[mid].push_back(i); } for(int i=m-1;i>=0;i--) { Union(e[i].u,e[i].v); for(auto&id:query[i]) { if(Find(s[id])==Find(t[id])) { res[id]=e[i].w; l[id]=i+1; } else r[id]=i-1; } } } for(int i=1;i<=q;i++) cout<<res[i]<<'\n'; } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */
#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...