제출 #863075

#제출 시각아이디문제언어결과실행 시간메모리
863075Dec0DeddEvacuation plan (IZhO18_plan)C++14
100 / 100
1696 ms51640 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5+100; const long long INF = 1e9; const int K = 40; typedef long long ll; typedef pair<ll, ll> pii; vector<pii> G[N]; ll d[N], n, m, k, q, ans[N], lq[N], rq[N], s[N], t[N]; struct dsu { vector<int> p; void init(int sz) { p.resize(sz+10); for (int i=0; i<sz+10; ++i) p[i]=i; } int f(int x) { if (p[x] == x) return x; return p[x]=f(p[x]); } void mrg(int x, int y) { x=f(x), y=f(y); if (x == y) return; p[x]=y; } }; void dijk(vector<int> s) { for (int i=0; i<=n; ++i) d[i]=INF; priority_queue<pii, vector<pii>, greater<pii>> pq; for (auto u : s) d[u]=0, pq.push({0, u}); while (!pq.empty()) { pii x=pq.top(); pq.pop(); int v=x.second; if (x.first > d[v]) continue; for (auto u : G[v]) { if (d[u.second] > d[v]+u.first) { d[u.second]=d[v]+u.first; pq.push({d[u.second], u.second}); } } } } vector<pii> wghs; void solve(int q) { for (int i=1; i<=q; ++i) wghs.push_back({(lq[i]+rq[i])/2, -i}); for (int z=0; z<K; ++z) { dsu ds; ds.init(n+1); sort(wghs.begin(), wghs.end(), greater<pii>()); for (auto &u : wghs) { if (u.second > 0) { int i=u.second; for (auto v : G[i]) { if (d[v.second] >= u.first) ds.mrg(i, v.second); } } else { int i=-u.second; if (lq[i] > rq[i]) continue; if (ds.f(s[i]) == ds.f(t[i])) { ans[i]=max(ans[i], u.first); lq[i]=u.first+1; } else rq[i]=u.first-1; u.first=(lq[i]+rq[i])/2; } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cin>>n>>m; for (int i=1; i<=m; ++i) { ll a, b, w; cin>>a>>b>>w; G[a].push_back({w, b}); G[b].push_back({w, a}); } cin>>k; vector<int> g; for (int i=1; i<=k; ++i) { int x; cin>>x; g.push_back(x); } dijk(g); for (int i=1; i<=n; ++i) assert(d[i] < INF); cin>>q; for (int i=1; i<=n; ++i) wghs.push_back({d[i], i}); for (int i=1; i<=q; ++i) { cin>>s[i]>>t[i]; lq[i]=0, rq[i]=INF; } solve(q); for (int 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...