제출 #1112628

#제출 시각아이디문제언어결과실행 시간메모리
1112628dostsEvacuation plan (IZhO18_plan)C++17
100 / 100
339 ms43456 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define vi vector<int> #define all(xx) xx.begin(),xx.end() #define ps(xxx) cout << (xxx) << endl; const int N = 5e2+1,inf = 1e16,MOD = 1e9+7; struct DSU { vi dad,change,sz; DSU(int nn) { dad.resize(nn+1); iota(dad.begin(),dad.end(),0); change.assign(nn+1,-1); sz.assign(nn+1,1); } int find(int x,int t) { if (change[x] == -1 || t < change[x]) return x; return find(dad[x],t); } void unite(int x,int y,int t) { int a = find(x,t); int b = find(y,t); if (a == b) return; if (sz[a] > sz[b]) swap(a,b); dad[a] = b; change[a] = t; sz[b]+=sz[a]; } }; void solve() { int n,m; cin >> n >> m; vector<pii> edges[n+1]; for (int i=1;i<=m;i++) { int a,b,c; cin >> a >> b >> c; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } int k; cin >> k; vi dist(n+1,inf); priority_queue<pii,vector<pii>,greater<pii>> pq; for (int i=1;i<=k;i++) { int c; cin >> c; pq.push({0,c}); dist[c] = 0; } while (!pq.empty()) { pii f= pq.top(); pq.pop(); if (dist[f.ss] < f.ff) continue; for (auto it : edges[f.ss]) { if (dist[it.ff] > f.ff+it.ss) { dist[it.ff] = f.ff+it.ss; pq.push({f.ff+it.ss,it.ff}); } } } vector<int> ord(n+1); iota(ord.begin(),ord.end(),0); sort(ord.begin()+1,ord.end(),[&](int x,int y){ return dist[x] > dist[y]; }); DSU dsu(n); vi active(n+1,0); for (int i=1;i<=n;i++) { int vert = ord[i]; active[vert] = 1; for (auto it : edges[vert]) { if (active[it.ff]) dsu.unite(vert,it.ff,i); } } int q; cin >> q; while (q--) { int x,y; cin >> x >> y; int l = 1; int r = n; while (l<=r) { int m = (l+r) >> 1; if (dsu.find(x,m) == dsu.find(y,m)) r = m-1; else l = m+1; } cout << dist[ord[l]] << '\n'; } } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#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...