제출 #213615

#제출 시각아이디문제언어결과실행 시간메모리
213615someone_aaEvacuation plan (IZhO18_plan)C++17
100 / 100
1064 ms29412 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define pii pair<int,int> using namespace std; const int maxn = 100100; class dsu { public: int uparent[maxn], n; int usize[maxn]; void init(int _n) { n = _n; for(int i=0;i<=n;i++) { uparent[i] = i; usize[i] = 1; } } int ufind(int x) { while(x != uparent[x]) x = uparent[x]; return x; } void unite(int x, int y) { x = ufind(x); y = ufind(y); if(x == y) return; if(usize[x] > usize[y]) { uparent[y] = x; usize[x] += usize[y]; } else { uparent[x] = y; usize[y] += usize[x]; } } }D; int n, m, k, q, sz; int result[maxn]; int dist[maxn]; bool visited[maxn]; vector<int>v; // NPP indexes vector<pair<int,int> > g[maxn]; void get_distances() { for(int i=0;i<=n;i++) { visited[i] = false; dist[i] = INT_MAX; } priority_queue<pii, vector<pii>, greater<pii> > pq; for(int i:v) { dist[i] = 0; pq.push(mp(0, i)); } while(!pq.empty()) { int node = pq.top().second; int curr = pq.top().first; pq.pop(); if(visited[node]) continue; visited[node] = true; for(auto i:g[node]) { if(!visited[i.first] && dist[i.first] > curr + i.second) { dist[i.first] = curr + i.second; pq.push(mp(dist[i.first], i.first)); } } } } int orgval[maxn]; vector<int>indexes[maxn]; map<int, int>cind; set<int>st; void preprocess() { for(int i=1;i<=n;i++) { st.insert(dist[i]); } int br = 0; for(int i:st) { cind[i] = br; orgval[br] = i; br++; } sz = br; for(int i=1;i<=n;i++) { indexes[cind[dist[i]]].pb(i); } } int ql[maxn], qr[maxn]; int qs[maxn], qt[maxn]; bool answ[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; int a, b, c; for(int i=0;i<m;i++) { cin>>a>>b>>c; g[a].pb(mp(b, c)); g[b].pb(mp(a, c)); } int x; cin>>k; for(int i=0;i<k;i++) { cin>>x; v.pb(x); } get_distances(); preprocess(); cin>>q; for(int i=1;i<=q;i++) { cin>>qs[i]>>qt[i]; ql[i] = -1, qr[i] = sz; } for(int d=0;d<20;d++) { //cout<<"At level: "<<d<<"\n"; D.init(n); vector<int>qrs[maxn]; memset(answ,false,sizeof(answ)); //cout<<"Queries at beginning\n"; for(int i=1;i<=q;i++) { int mid = (ql[i] + qr[i]) / 2; if(qr[i] - ql[i] <= 1) { result[i] = orgval[ql[i]]; continue; } qrs[mid].pb(i); } for(int j=sz-1;j>=0;j--) { for(int i:indexes[j]) { for(auto nxt:g[i]) { if(dist[i] <= dist[nxt.first]) { D.unite(i, nxt.first); } } } for(int i:qrs[j]) { if(D.ufind(qs[i]) == D.ufind(qt[i])) { answ[i] = true; } } } for(int i=1;i<=q;i++) { if(qr[i] - ql[i] <= 1) continue; int mid = (ql[i] + qr[i]) / 2; if(answ[i]) { ql[i] = mid; } else { qr[i] = mid; } } } for(int i=1;i<=q;i++) { cout<<result[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...