Submission #1209122

#TimeUsernameProblemLanguageResultExecution timeMemory
1209122lopkusEvacuation plan (IZhO18_plan)C++20
100 / 100
435 ms73460 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn = 2e5 + 5; //dsu rollback + parallel binary search struct DSU{ vector<pair<int, int>> past_p, past_sz; vector<int> st; int p[maxn], sz[maxn]; void init(){ for(int i = 1; i < maxn; i++){ p[i] = i; sz[i] = 1; } } int find(int u){ return (p[u] == u ? u : find(p[u])); } void unon(int a, int b){ a = find(a); b = find(b); if(sz[a] < sz[b]) swap(a, b); past_sz.push_back({a, sz[a]}); past_p.push_back({b, p[b]}); if(a != b){ sz[a] += sz[b]; p[b] = a; } } void rollback(){ } void save(){ st.push_back(past_p.size()); } void to_last(){ while(past_p.size() != st.back()){ p[past_p.back().first] = past_p.back().second; sz[past_sz.back().first] = past_sz.back().second; past_p.pop_back(); past_sz.pop_back(); } st.pop_back(); } } dsu; int ans[maxn], s[maxn], t[maxn], pos[maxn]; vector<pair<int, int>> adj[maxn]; vector<int> comp, all; void solve(int l, int r, vector<int>& cur){ if(l == r) for(int i: cur) ans[i] = l; else{ dsu.save(); int mid = (l + r) / 2; for(int i = l; i <= mid; i++){ for(auto [v, w]: adj[comp[i]]){ if(pos[v] <= mid) dsu.unon(comp[i], v); } } vector<int> le, ri; for(int i: cur){ if(dsu.find(s[i]) == dsu.find(t[i])) le.push_back(i); else ri.push_back(i); } if(mid < r && ri.size()) solve(mid + 1, r, ri); dsu.to_last(); if(le.size()) solve(l, mid, le); } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector<int> d(n + 1, 1e9); for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } int k; cin >> k; priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int i = 0; i < k; i++){ int x; cin >> x; d[x] = 0; pq.push({0, x}); } while(!pq.empty()){ auto [curw, u] = pq.top(); pq.pop(); if(d[u] != curw) continue; for(auto [v, w]: adj[u]){ if(d[v] > curw + w){ d[v] = curw + w; pq.push({d[v], v}); } } } for(int i = 1; i <= n; i++) comp.push_back(i); sort(comp.begin(), comp.end(), [&](int x, int y){ return d[x] > d[y]; }); int q; cin >> q; for(int i = 0; i < q; i++){ cin >> s[i] >> t[i]; all.push_back(i); } for(int i = 0; i < n; i++) pos[comp[i]] = i; dsu.init(); solve(0, n - 1, all); for(int i = 0; i < q; i++) cout << d[comp[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...