제출 #1093087

#제출 시각아이디문제언어결과실행 시간메모리
10930874QT0REvacuation plan (IZhO18_plan)C++17
100 / 100
406 ms78700 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> vector<pll> graph[100003]; array<ll,3> edges[500003]; ll dist[100003]; bool NPP[100003]; ll oo=1e18; void Dijkstra(ll n){ priority_queue<pll,vector<pll>,greater<pll>> pq; fill(dist,dist+n+1,oo); for (ll i = 1; i<=n; i++)if (NPP[i]){ dist[i]=0; pq.push({0,i}); } while(pq.size()){ auto [d,v] = pq.top(); pq.pop(); if (d!=dist[v])continue; for (auto [u,c] : graph[v]){ if (d+c<dist[u]){ dist[u]=d+c; pq.push({dist[u],u}); } } } } ll lider[100003]; ll siz[100003]; ll Find(ll v){ return lider[v]==v?lider[v]:(lider[v]=Find(lider[v])); } void Union(ll a, ll b){ a=Find(a); b=Find(b); if (a==b)return; if (siz[a]<siz[b])swap(a,b); lider[b]=a; siz[a]+=siz[b]; } struct zap{ ll l; ll p; ll st; ll nd; }; vector<ll> query[100003]; zap dane[500003]; vector<ll> dl; ll ans[500003]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,m,k,q; cin >> n >> m; for (ll i = 1; i<=m; i++){ cin >> edges[i][0] >> edges[i][1] >> edges[i][2]; graph[edges[i][0]].push_back({edges[i][1],edges[i][2]}); graph[edges[i][1]].push_back({edges[i][0],edges[i][2]}); } cin >> k; for (ll i = 1,v; i<=k; i++){ cin >> v; NPP[v]=true; } Dijkstra(n); for (ll i = 1; i<=m; i++)edges[i][2]=min(dist[edges[i][0]],dist[edges[i][1]]); sort(edges+1,edges+m+1,[](array<ll,3> a, array<ll,3> b){return a[2]>b[2];}); dl.push_back(-1); for (ll i = 1; i<=n; i++)dl.push_back(dist[i]); sort(dl.begin(),dl.end()); cin >> q; for (ll i = 1; i<=q; i++){ cin >> dane[i].st >> dane[i].nd; dane[i].l=0; dane[i].p=dl.size()-1; query[dl.size()/2].push_back(i); } ll lft=q; while(lft){ for (ll i = 1; i<=n; i++){ lider[i]=i; siz[i]=1; } ll iter=1; for (ll i = dl.size()-1; i>=0; i--){ while(iter<=m && edges[iter][2]>=dl[i]){ Union(edges[iter][0],edges[iter][1]); iter++; } while(query[i].size()){ ll now=query[i].back(); query[i].pop_back(); if (dane[now].l==dane[now].p){ ans[now]=dl[i]; lft--; continue; } if (Find(dane[now].st)==Find(dane[now].nd))dane[now].l=i; else dane[now].p=i-1; query[(dane[now].l+dane[now].p+1)/2].push_back(now); } } } for (ll i = 1; i<=q; i++)cout << ans[i] << '\n'; }
#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...