| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890052 | Alfraganus | Evacuation plan (IZhO18_plan) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<vector<pair<int, int> > > g;
using ll = long long;
vector<int> rt;
vector<set<int> > lst;
int root(int u){
return u == rt[u] ? u : rt[u] = root(rt[u]);
}
int main(){
int n, m;
cin >> n >> m;
vector<pair<int, pair<int, int> > > ways;
g.resize(n+1);
rt.resize(n+1);
lst.resize(n+1);
for(int i = 1; i <= n; i ++) rt[i] = i;
ways.resize(m);
for(int i = 0, u, v, w; i < m; i ++){
cin >> u >> v >> w;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
ways[i] = {w, {u, v}};
}
vector<ll> h(n+1, LLONG_MAX);
set<pair<int, int> > q;
int k, x;
for(cin >> k; k > 0; k --){
cin >> x;
h[x] = 0;
q.emplace(0, x);
}
while(!q.empty()){
auto [w, u] = *q.begin();
q.erase(q.begin());
for(auto v:g[u])
if(h[v.first] > h[u] + v.second){
q.erase({h[v.first], v.first});
h[v.first] = h[u] + v.second;
q.emplace(h[v.first], v.first);
}
}
for(int i = 0; i < m; i ++)
ways[i].first = min(h[ways[i].second.first], h[ways[i].second.second]);
sort(ways.rbegin(), ways.rend());
int qu;
cin >> qu;
vector<ll> res(qu);
for(int i = 0, u, v; i < qu; i ++){
cin >> u >> v;
lst[u].insert(i);
lst[v].insert(i);
}
for(auto [w,y]: ways){
auto [u, v] = y;
u = root(u);
v = root(v);
if(u == v) continue;
if(lst[u].size() > lst[v].size()) swap(u, v);
for(int q:lst[u]){
if(lst[v].count(q)){
res[q] = w;
lst[v].erase(q);
}
else
lst[v].insert(q);
}
lst[u].clear();
rt[u] = v;
}
for(ll x:res) cout << x << '\n';
return 0;
}