Submission #890055

#	Time	Username	Problem	Language	Result	Execution time	Memory
890055		Alfraganus	Evacuation plan (IZhO18_plan)	C++17	100 / 100	537 ms	38224 KiB

plan

#include <bits/stdc++.h>
#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(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
    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;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46